背景
Dijkstra 算法是处理单源最短路径的有效算法，但它对存在负权回路的图就会失效。这时候，就需要使用其他的算法来应对这个问题，Bellman-Ford（中文名：贝尔曼 - 福特）算法就是其中一个。
Bellman-Ford 算法不仅可以求出最短路径，也可以检测负权回路的问题。该算法由美国数学家理查德 • 贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特 • 福特（Lester Ford）发明。
算法过程分析
对于一个不存在负权回路的图，Bellman-Ford 算法求解最短路径的方法如下：
设其顶点数为 n，边数为 m。设其源点为 source，数组dist[i]记录从源点 source 到顶点 i 的最短路径，除了dist[source]初始化为 0 外，其它dist[]皆初始化为 MAX。以下操作循环执行 n-1 次：
对于每一条边 arc(u, v)，如果 dist[u] + w(u, v) < dist[v]，则使 dist[v] = dist[u] + w(u, v)，其中 w(u, v) 为边 arc(u, v) 的权值。
n-1 次循环，Bellman-Ford 算法就是利用已经找到的最短路径去更新其它点的dist[]。
接下来再看看 Bellman-Ford 算法是如何检测负权回路的？
检测的方法很简单，只需在求解最短路径的 n-1 次循环基础上，再进行第 n 次循环：
对于所有边，只要存在一条边 arc(u, v) 使得 dist[u] + w(u, v) < dist[v]，则该图存在负权回路，其中 w(u, v) 为边 arc(u, v) 的权值。
完整代码
/**
*
* author : 刘毅（Limer）
* date : 2017-05-21
* mode : C++
*/
#include <iostream>
#include <stack>
using namespace std;
#define MAX 10000 // 假设权值最大不超过 10000
struct Edge
{
int u;
int v;
int w;
};
Edge edge[10000]; // 记录所有边
int dist[100]; // 源点到顶点 i 的最短距离
int path[100]; // 记录最短路的路径
int vertex_num; // 顶点数
int edge_num; // 边数
int source; // 源点
bool BellmanFord()
{
// 初始化
for (int i = 0; i < vertex_num; i++)
dist[i] = (i == source) ? 0 : MAX;
// n-1 次循环求最短路径
for (int i = 1; i <= vertex_num - 1; i++)
{
for (int j = 0; j < edge_num; j++)
{
if (dist[edge[j].v] > dist[edge[j].u] + edge[j].w)
{
dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
path[edge[j].v] = edge[j].u;
}
}
}
bool flag = true; // 标记是否有负权回路
// 第 n 次循环判断负权回路
for (int i = 0; i < edge_num; i++)
{
if (dist[edge[i].v] > dist[edge[i].u] + edge[i].w)
{
flag = false;
break;
}
}
return flag;
}
void Print()
{
for (int i = 0; i < vertex_num; i++)
{
if (i != source)
{
int p = i;
stack<int> s;
cout << "顶点 " << source << " 到顶点 " << p << " 的最短路径是： ";
while (source != p) // 路径顺序是逆向的，所以先保存到栈
{
s.push(p);
p = path[p];
}
cout << source;
while (!s.empty()) // 依次从栈中取出的才是正序路径
{
cout << "--" << s.top();
s.pop();
}
cout << " 最短路径长度是：" << dist[i] << endl;
}
}
}
int main()
{
cout << "请输入图的顶点数，边数，源点：";
cin >> vertex_num >> edge_num >> source;
cout << "请输入" << edge_num << "条边的信息：n";
for (int i = 0; i < edge_num; i++)
cin >> edge[i].u >> edge[i].v >> edge[i].w;
if (BellmanFord())
Print();
else
cout << "Sorry,it have negative circle!n";
return 0;
}
执行截图：
算法优化
以下除非特殊说明，否则都默认是不存在负权回路的。
先来看看 Bellman-Ford 算法为何需要循环 n-1 次来求解最短路径？
读者可以从 Dijkstra 算法来考虑，想一下，Dijkstra 从源点开始，更新dist[]，找到最小值，再更新dist[] ，，，每次循环都可以确定一个点的最短路。
Bellman-Ford 算法同样也是这样，它的每次循环也可以确定一个点的最短路，只不过代价很大，因为 Bellman-Ford 每次循环都是操作所有边。
既然代价这么大，相比 Dijkstra 算法，Bellman-Ford 算法还有啥用？因为后者可以检测负权回路啊。
Bellman-Ford 算法的时间复杂度为 O(nm)，其中 n 为顶点数，m 为边数。
O(nm) 的时间，大多数都浪费了。考虑一个随机图（点和边随机生成），除了已确定最短路的顶点与尚未确定最短路的顶点之间的边，其它的边所做的都是无用的，大致描述为下图（分割线以左为已确定最短路的顶点）：
其中红色部分为所做无用的边，蓝色部分为实际有用的边。
（本文由中国计算网总编栾玲收录《超算AI数据库》 转载请注明出处）
微信关注公众号“cncompute_com ”，每天为您奉上最新最热的计算头条资讯，满满干货~多年软件设计师经历，业内资深分析人士，圈中好友众多，信息丰富，观点独到。发布各大自媒体平台，覆盖百万读者。《苹果的品牌设计之道》、《谁拥有未来：小米互联网思维PK传统行业思维》二本畅销书作者栾玲，现为中国计算网设计总监与内容总编，栾玲专著与国画已被国图、清华北大图书馆等收藏