Bellman-Ford算法

Bellman-Ford算法的优点是可以发现负圈，缺点是时间复杂度比Dijkstra算法高。而SPFA算法是使用队列优化的Bellman-Ford版本，其在时间复杂度和编程难度上都比其他算法有优势。

Bellman-Ford算法流程分为三个阶段：

• 第一步：数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为INF, Distant[s]为0；

• 第二步：以下操作循环执行至多n-1次，n为顶点数： 对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值； 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

• 第三步：为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

v的最短距离保存在 d[v]中。

在这个算法中，需要了解的几点

1、只有上一次迭代中松驰过的点才有可能参与下一次迭代的松弛操作。

似乎算法在遍历每一条边的做法会浪费时间，或许我们只需要考虑那些被成功松弛的点的邻点就可以了。我们可以用一个队列来维护这些被成功松弛的点，这个小小的改进可以节省很多时间，改进后的算法叫做SPFA。

2、迭代的实际意义：每一次迭代k中，我们找到了经历了k条边的最短路

3、没有点能够松弛时，迭代结束

Bellman-Ford(G,w,s) ：boolean   //图G ，边集 函数 w ，s为源点for each vertex v ∈ V（G） do        //初始化 1阶段d[v] ←+∞d[s] ←0;                             //1阶段结束for i=1 to |v|-1 do               //2阶段开始，双重循环。for each edge（u,v） ∈E(G) do //边集数组要用到，穷举每条边。If d[v]> d[u]+ w(u,v) then      //松弛判断d[v]=d[u]+w(u,v)               //松弛操作   2阶段结束for each edge（u,v） ∈E(G) doIf d[v]> d[u]+ w(u,v) thenExit falseExit true

SPFA

算法特点：在 Bellman-ford 算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

关键词：初始化，relax，队列

实现的过程和Bellman_Ford类似

【初始化】

dis数组全部赋值为INF，pre数组全部赋值为-1（表示还不知道前驱），

dis[s] = 0 表示源点不要求最短路径（或者最短路径就是0）。

【队列+松弛操作】

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队，这样不断从队列中取出顶点来进行松弛操作。

以此循环，直到队空为止就完成了单源最短路的求解。

【算法过程】

设立一个队列用来保存待优化的顶点，优化时每次取出队首顶点 u，并且用 u 点当前的最短路径估计值dis[u]对与 u 点邻接的顶点 v 进行松弛操作，如果 v 点的最短路径估计值dis[v]可以更小，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。

【检测负权回路】

方法：如果某个点进入队列的次数大于等于 n，则存在负权回路，其中 n 为图的顶点数。

#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <cstdio>
#include <functional>
using namespace std;const int maxn = 99999999;
int map[205][205];//邻接矩阵
int d[205];//源点到顶点i的最短距离
bool vis[205];//标记数组
int enqueue_num[205];//记录入队次数
int path[205];//记录最短的路径
int n;//顶点数
int e;//边数
int start;//源点bool SPFA()
{memset(vis,false,sizeof(vis));memset(enqueue_num,0,sizeof(enqueue_num));for(int i=0;i<n;i++){d[i] = maxn;path[i] = start;}queue<int> Q;Q.push(start);d[start] = 0;vis[start] = 1;enqueue_num[start]++;int v;while(Q.empty()!=1){int u = Q.front();Q.pop();vis[u] = 0;for(v=0;v<n;v++){if(map[u][v]!=maxn)//u 与 v 直接邻接{if(d[u]+map[u][v]<d[v]){d[v] = d[u] + map[u][v];path[v] = u;if(!vis[v]){Q.push(v);enqueue_num[v]++;if(enqueue_num[v]>=n){return false;}vis[v] = true;}}}}}return true;
}void print()
{int i;for(i=0;i<n;i++){if(i!=start){int p = i;stack<int> s;cout << "顶点 " << start << " 到顶点 " << p << "最短路是：";while(start!=p){s.push(p);p=path[p];}cout << start;while(s.empty()!=1){cout << "---" << s.top();s.pop();}cout << "    最短路径的长度是：" << d[i] << endl; }}
}int main()
{int i, j;cout << "请输入图的顶点数，边数，源点：\n";cin >> n >> e >> start;//初始化for(i=0;i<=n;i++){for(j=0;j<=n;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = maxn;}}cout << "请输入" << e << "条边的信息：\n";int u, v, w;//默认是有向图for(i=0;i<e;i++){cin >> u >> v >> w;map[u][v] = w;}if(SPFA())print();elsecout << "Sorry,it has negative circle!\n";return 0;
}

用下面这张图进行测试数据：

现学现用

http://poj.org/problem?id=3259

【问题描述】

虫洞是很奇特的，因为它是一个**单向**通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以，他会为你提供F个农场的完整的图（1≤F≤5）。所有的路径所花时间都不大于10000秒，所有的虫洞都回到不大于10000秒之前。

【Input】

第1行：一个整数F表示接下来会有F个农场说明。 每个农场第一行：分别是三个空格隔开的整数：N，M和W 第2行到M+1行：三个空格分开的数字（S，E，T）描述，分别为：需要T秒走过S和E之间的双向路径。两个区域可能由一个以上的路径来连接。 第M +2到M+ W+1行：三个空格分开的数字（S，E，T）描述虫洞，描述单向路径，S到E且回溯T秒。

【Output】

F行，每行代表一个农场 每个农场单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求

【样例输入】

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

【样例输出】

NO
YES

题意是问是否能通过虫洞回到过去；虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退T秒。我们把虫洞看成是一条负权路，问题就转化成求一个图中是否存在负权回路；

Bellman_ford 算法解题

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 9999999;typedef struct Edge
{int u,v;int weight;
}Edge;
Edge edge[5200]; 
int d[1010];
int N,M,W,F,all_e;bool bellman_ford()
{int i,j;bool flag;for(i=1;i<=N-1;i++){flag = false;for(j=0;j<all_e;j++){if(d[edge[j].v]>d[edge[j].u]+edge[j].weight){d[edge[j].v]=d[edge[j].u]+edge[j].weight;flag = true;}}if(!flag)	return false;//不存在负环}for(i=0;i<all_e;i++){if(d[edge[i].v]>d[edge[i].u]+edge[i].weight)return true;//存在}return false;
}int main()
{int i,j;cin >> F;while(F--){cin >> N >> M >> W;memset(d,maxn,sizeof(d));all_e = 0;int u,v,w;//注意是无向图,双向的for(i=1;i<=M;i++){cin >> u >> v >> w;edge[all_e].u = u;edge[all_e].v = v;edge[all_e++].weight = w;edge[all_e].u = v;edge[all_e].v = u;edge[all_e++].weight = w;}//题目中明确指出，虫洞是单向的for(i=1;i<=W;i++){cin >> u >> v >> w;edge[all_e].u = u;edge[all_e].v = v;edge[all_e++].weight = -w;}if(bellman_ford())cout << "YES\n";elsecout << "NO\n";}return 0;
}

Floyd算法

也可以求解，但是，很容易就超时，AC的话时间也会比Bellman_ford算法多很多

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;const int maxn = 99999999;
int map[520][520];
int F,N,M,W;bool bellman_ford()
{int i,j,k;for(k=1;k<=N;k++){for(i=1;i<=N;i++){for(j=1;j<=N;j++){if(map[i][j]>map[i][k]+map[k][j]){map[i][j]=map[i][k]+map[k][j];}}if(map[i][i]<0){return true;}}}return false;
}int main()
{int i,j;cin >> F;while(F--){cin >> N >> M >> W;for(i=0;i<=N;i++){for(j=0;j<=N;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = maxn;}}int a,b,w;//需要注意的是：正权的边是单向的，负权的边是双向的。for(i=1;i<=M;i++){cin >> a >> b >> w;if(map[a][b]>w){map[a][b] = w;map[b][a] = w;}}for(i=1;i<=W;i++){cin >> a >> b >> w;map[a][b] = -w;}if(bellman_ford())cout << "YES\n";elsecout << "NO\n";}return 0;
}

SPFA（Bellman_ford + 队列 优化）

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;const int maxn = 9999999;
int map[520][520];
int d[520];
bool vis[520];
int enqueue_num[520];
int M,N,W;
int F;bool SPFA()
{memset(vis,false,sizeof(vis));memset(enqueue_num,0,sizeof(enqueue_num));memset(d,maxn,sizeof(d));queue<int> Q;Q.push(1);d[1] = 0;vis[1] = true;enqueue_num[1]++;int v;while(Q.empty()!=1){int u = Q.front();Q.pop();vis[u] = false;for(v=1;v<=N;v++){if(map[u][v]!=maxn){if(d[u]+map[u][v]<d[v]){d[v]=d[u]+map[u][v];if(!vis[v]){Q.push(v);enqueue_num[v]++;if(enqueue_num[v]>=N){return false;//有负圈}vis[v] = true;}}}}}return true;//没有负圈
}int main ()
{int i,j;cin >> F;while(F--){cin >> N >> M >> W;for(i=0;i<=N;i++){for(j=0;j<=N;j++){if(i==j)	map[i][j] = 0;else	map[i][j] = maxn;}}int a,b,c;for(i=1;i<=M;i++){cin >> a >> b >> c;if(map[a][b]>c){map[a][b] = c;map[b][a] = c;}}for(i=1;i<=W;i++){cin >> a >> b >> c;map[a][b] = -c;}if(SPFA())cout << "NO\n";elsecout << "YES\n";}return 0;
}

推荐博客：

最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)