背景
Dijkstra 算法是處理單源最短路徑的有效算法，但它對(duì)存在負(fù)權(quán)回路的圖就會(huì)失效。這時(shí)候，就需要使用其他的算法來(lái)應(yīng)對(duì)這個(gè)問(wèn)題，Bellman-Ford（中文名：貝爾曼 - 福特）算法就是其中一個(gè)。
Bellman-Ford 算法不僅可以求出最短路徑，也可以檢測(cè)負(fù)權(quán)回路的問(wèn)題。該算法由美國(guó)數(shù)學(xué)家理查德 • 貝爾曼（Richard Bellman, 動(dòng)態(tài)規(guī)劃的提出者）和小萊斯特 • 福特（Lester Ford）發(fā)明。
算法過(guò)程分析
對(duì)于一個(gè)不存在負(fù)權(quán)回路的圖，Bellman-Ford 算法求解最短路徑的方法如下：
設(shè)其頂點(diǎn)數(shù)為 n，邊數(shù)為 m。設(shè)其源點(diǎn)為 source，數(shù)組dist[i]記錄從源點(diǎn) source 到頂點(diǎn) i 的最短路徑，除了dist[source]初始化為 0 外，其它dist[]皆初始化為 MAX。以下操作循環(huán)執(zhí)行 n-1 次：
對(duì)于每一條邊 arc(u, v)，如果 dist[u] + w(u, v) < dist[v]，則使 dist[v] = dist[u] + w(u, v)，其中 w(u, v) 為邊 arc(u, v) 的權(quán)值。
n-1 次循環(huán)，Bellman-Ford 算法就是利用已經(jīng)找到的最短路徑去更新其它點(diǎn)的dist[]。
接下來(lái)再看看 Bellman-Ford 算法是如何檢測(cè)負(fù)權(quán)回路的？
檢測(cè)的方法很簡(jiǎn)單，只需在求解最短路徑的 n-1 次循環(huán)基礎(chǔ)上，再進(jìn)行第 n 次循環(huán)：
對(duì)于所有邊，只要存在一條邊 arc(u, v) 使得 dist[u] + w(u, v) < dist[v]，則該圖存在負(fù)權(quán)回路，其中 w(u, v) 為邊 arc(u, v) 的權(quán)值。
完整代碼
/**
*
* author : 劉毅（Limer）
* date : 2017-05-21
* mode : C++
*/
#include <iostream>
#include <stack>
using namespace std;
#define MAX 10000 // 假設(shè)權(quán)值最大不超過(guò) 10000
struct Edge
{
int u;
int v;
int w;
};
Edge edge[10000]; // 記錄所有邊
int dist[100]; // 源點(diǎn)到頂點(diǎn) i 的最短距離
int path[100]; // 記錄最短路的路徑
int vertex_num; // 頂點(diǎn)數(shù)
int edge_num; // 邊數(shù)
int source; // 源點(diǎn)
bool BellmanFord()
{
// 初始化
for (int i = 0; i < vertex_num; i++)
dist[i] = (i == source) ? 0 : MAX;
// n-1 次循環(huán)求最短路徑
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; // 標(biāo)記是否有負(fù)權(quán)回路
// 第 n 次循環(huán)判斷負(fù)權(quá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 << "頂點(diǎn) " << source << " 到頂點(diǎn) " << p << " 的最短路徑是： ";
while (source != p) // 路徑順序是逆向的，所以先保存到棧
{
s.push(p);
p = path[p];
}
cout << source;
while (!s.empty()) // 依次從棧中取出的才是正序路徑
{
cout << "--" << s.top();
s.pop();
}
cout << " 最短路徑長(zhǎng)度是：" << dist[i] << endl;
}
}
}
int main()
{
cout << "請(qǐng)輸入圖的頂點(diǎn)數(shù)，邊數(shù)，源點(diǎn)：";
cin >> vertex_num >> edge_num >> source;
cout << "請(qǐng)輸入" << 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;
}
執(zhí)行截圖：
算法優(yōu)化
以下除非特殊說(shuō)明，否則都默認(rèn)是不存在負(fù)權(quán)回路的。
先來(lái)看看 Bellman-Ford 算法為何需要循環(huán) n-1 次來(lái)求解最短路徑？
讀者可以從 Dijkstra 算法來(lái)考慮，想一下，Dijkstra 從源點(diǎn)開(kāi)始，更新dist[]，找到最小值，再更新dist[] ，，，每次循環(huán)都可以確定一個(gè)點(diǎn)的最短路。
Bellman-Ford 算法同樣也是這樣，它的每次循環(huán)也可以確定一個(gè)點(diǎn)的最短路，只不過(guò)代價(jià)很大，因?yàn)?Bellman-Ford 每次循環(huán)都是操作所有邊。
既然代價(jià)這么大，相比 Dijkstra 算法，Bellman-Ford 算法還有啥用？因?yàn)楹笳呖梢詸z測(cè)負(fù)權(quán)回路啊。
Bellman-Ford 算法的時(shí)間復(fù)雜度為 O(nm)，其中 n 為頂點(diǎn)數(shù)，m 為邊數(shù)。
O(nm) 的時(shí)間，大多數(shù)都浪費(fèi)了?？紤]一個(gè)隨機(jī)圖（點(diǎn)和邊隨機(jī)生成），除了已確定最短路的頂點(diǎn)與尚未確定最短路的頂點(diǎn)之間的邊，其它的邊所做的都是無(wú)用的，大致描述為下圖（分割線以左為已確定最短路的頂點(diǎn)）：
其中紅色部分為所做無(wú)用的邊，藍(lán)色部分為實(shí)際有用的邊。
（本文由中國(guó)計(jì)算網(wǎng)總編欒玲收錄《超算AI數(shù)據(jù)庫(kù)》 轉(zhuǎn)載請(qǐng)注明出處）
微信關(guān)注公眾號(hào)“cncompute_com ”，每天為您奉上最新最熱的計(jì)算頭條資訊，滿滿干貨~多年軟件設(shè)計(jì)師經(jīng)歷，業(yè)內(nèi)資深分析人士，圈中好友眾多，信息豐富，觀點(diǎn)獨(dú)到。發(fā)布各大自媒體平臺(tái)，覆蓋百萬(wàn)讀者?！短O果的品牌設(shè)計(jì)之道》、《誰(shuí)擁有未來(lái)：小米互聯(lián)網(wǎng)思維PK傳統(tǒng)行業(yè)思維》二本暢銷書作者欒玲，現(xiàn)為中國(guó)計(jì)算網(wǎng)設(shè)計(jì)總監(jiān)與內(nèi)容總編，欒玲專著與國(guó)畫已被國(guó)圖、清華北大圖書館等收藏