最短路问题是什么
最短路问题是指：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值 之和最小的路径。
解决最短路的问题的算法有：
Bellman_Ford算法
Dijkstra算法
Floyed算法
SPFA算法
Bellman_Ford算法
原理
-
松弛
每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短**。
-
负权值判定
图的最大深度为，如果第次循环中仍有节点的最短距离发生代表，说明有父权值环
-
循环的提前跳出
在某次循环不再进行松弛时，直接退出循环。
过程
-
初始化
原点的距离初始化为0，其他点的距离初始化为INF
-
循环
-
每次循环遍历所有边，进行松弛操作，如果满足
则需要进行松弛操作。
每次循环完之后判断是否有节点的距离更新，如果没有提前退出循环。
在第次循环之后判断是否有节点的距离更新，如果有，说明负权值环。
-
优点和缺点
-
优点
实现简单
可以处理权值为负的图
-
缺点
- 时间复杂度高
代码
bool Bellman_Ford(int s){
for(int i = 0; i < vNum; i++) d[i] = INF;//初始化
d[s] = 0;
int cnt = 1;//记录循环的次数
while(true){
bool update = false;
for(int i = 0; i < eNum; i++){
struct Edge e = edges[i];
if((d[e.from] != INF) && (d[e.to] > d[e.from] + e.w)){
update = true;
d[e.to] = d[e.from] + e.w;
}
}
if(!update) break;//没有节点的最短距离改变，提前退出循环
++cnt;
if(cnt == vNum + 1) return false;//如果第|V|次循环仍有节点的最短距离改变，说明有负权值环
}
return true;
}
Dijkstra算法
Dijkstra算法的引出
考虑没有负权值边的情况。在Bellman_Ford算法中，如果d[i]还不是最短距离的话，即使进行的更新，d[j]也不会变成最短距离。可以对算法做如下修改：
找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离
此后不需要更新I中的“最短距离已经确定的顶点
算法过程
-
初始化
原点的距离初始化为0，其他点的距离初始化为INF
-
循环
执行以下循环过程，知道所有节点的最小距离都求出
从未被确认求出最小距离的节点中选出距离最小的节点
将选出的节点标记为已访求出最小距离
更新选出的节点的邻居节点的距离
用邻接矩阵表示图
需要维护的数据结构有：
g[MAX_V][MAX_V]，g[i][j]=w表示从i指向j的边的权值为w(w=-1时表示没有从i指向j的边)
visited[MAX_V]，visited[i]=1表示节点i的最小距离已经确认
d[MAX_V]，d[i]表示节点i的最小距离
取出最小距离的点时，遍历d数组，找出为最小距离未被确认的节点中，距离最小的点
更新邻居节点的距离时，遍历g[v]数组，更新v的邻居节点的距离
void Dijkstra(){
for(int i = 0; i < vNum; i++) d[i] = INF;
d[0] = 0;
while(true){
int v = -1;//seleted node with min d
//choose the node whose d is minimal
for(int i = 0; i < vNum; i++){
if(!visited[i] && (v == -1 || d[i] < d[v])) v = i;
}
//all nodes have been included
if(v == -1) break;
visited[v] = 1;
//update d of the v'neighbors
for(int i = 0; i < vNum; i++){
if(g[v][i] != -1 && (d[i] > d[v] + g[v][i])){
d[i] = d[v] + g[v][i];
}
}
}
print();
}
用邻接链表表示图
需要维护的数据结构有：
vector<p> g[MAX_V]，g[i]的类型是vector<p>，g[i]表示节点i的邻居节点
visited[MAX_V]，visited[i]=1表示节点i的最小距离已经确认
d[MAX_V]，d[i]表示节点i的最小距离
取出最小距离的点时，遍历d数组，找出为最小距离未被确认的节点中，距离最小的点
更新邻居节点的距离时，遍历gv，更新v的邻居节点的距离
void Dijkstra()
{
for(int i = 0; i < vNum; i++)
{
d[i] = INF;
}
d[0] = 0;
while(true)
{
int u = -1;
for(int i = 0; i < vNum; i++)
{
if(!visited[i] && (u == -1 || d[i] < d[u])) u = i;
}
if(u == -1) break;
visited[u] = 1;
vector<p>::iterator it;
for(it = g[u].begin(); it != g[u].end(); it++)
{
int v = (*it).first;
int w = (*it).second;
if(!visited[v] && (d[v] > d[u] + w))
{
d[v] = d[u] + w;
}
}
}
}
用链式向前星表示图
用链式向前星表示图，用优先级队列取出最小距离的节点
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> p;
const int INF = 10000;
const int MAX_V = 100;
const int MAX_E = 10000;
struct Edge{
int to;
int w;
int next;
};
//user defined comparer
struct mycmp{
bool operator()(p p1, p p2){
return p1.second > p2.second;
}
};
struct Edge edge[MAX_E];
int head[MAX_V];
int cnt;
int d[MAX_V];
int visited[MAX_V];
int vNum;
int eNum;
void addEdge(int u, int v, int w){
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void print(){
for(int i = 0; i < vNum; i++){
printf("%d d:%d\n", i, d[i]);
}
}
void Dijkstra(){
priority_queue<p, vector<p>, mycmp> q;//notice
for(int i = 0; i < vNum; i++){
d[i] = INF;
}
d[0] = 0;
q.push(make_pair(0, 0));
while(!q.empty()){
int u = q.top().first; q.pop();
printf("pop:%d d:%d\n", u, d[u]);
visited[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
int w = edge[i].w;
if(!visited[v] && (d[v] > d[u] + w)){
d[v] = d[u] + w;
q.push(make_pair(v, d[v]));
printf("push:%d d:%d\n", v, d[v]);
}
}
}
}
int main(){
memset(visited, 0, sizeof(visited));
memset(head, -1, sizeof(head));
cnt = 0;
scanf("%d %d", &vNum, &eNum);
for(int i = 0; i < eNum; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}
Dijkstra();
//print();
return 0;
}
