相關(guān)文章：
1.Dijkstra算法：
http://www.wutianqi.com/?p=1890
2.Floyd算法：
http://www.wutianqi.com/?p=1903
Dijkstra算法是處理單源最短路徑的有效算法，但它局限于邊的權(quán)值非負(fù)的情況，若圖中出現(xiàn)權(quán)值為負(fù)的邊，Dijkstra算法就會(huì)失效，求出的最短路徑就可能是錯(cuò)的。這時(shí)候，就需要使用其他的算法來(lái)求解最短路徑，Bellman-Ford算法就是其中最常用的一個(gè)。該算法由美國(guó)數(shù)學(xué)家理查德•貝爾曼（Richard Bellman, 動(dòng)態(tài)規(guī)劃的提出者）和小萊斯特•福特（Lester Ford）發(fā)明。Bellman-Ford算法的流程如下：
給定圖G(V, E)（其中V、E分別為圖G的頂點(diǎn)集與邊集），源點(diǎn)s，
- 數(shù)組Distant[i]記錄從源點(diǎn)s到頂點(diǎn)i的路徑長(zhǎng)度，初始化數(shù)組Distant[n]為, Distant[s]為0；
-
以下操作循環(huán)執(zhí)行至多n-1次，n為頂點(diǎn)數(shù)：
對(duì)于每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權(quán)值；
若上述操作沒(méi)有對(duì)Distant進(jìn)行更新，說(shuō)明最短路徑已經(jīng)查找完畢，或者部分點(diǎn)不可達(dá)，跳出循環(huán)。否則執(zhí)行下次循環(huán)；
- 為了檢測(cè)圖中是否存在負(fù)環(huán)路，即權(quán)值之和小于0的環(huán)路。對(duì)于每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負(fù)環(huán)路，即是說(shuō)改圖無(wú)法求出單源最短路徑。否則數(shù)組Distant[n]中記錄的就是源點(diǎn)s到各頂點(diǎn)的最短路徑長(zhǎng)度。
可知，Bellman-Ford算法尋找單源最短路徑的時(shí)間復(fù)雜度為O(V*E).
首先介紹一下松弛計(jì)算。如下圖：
松弛計(jì)算之前，點(diǎn)B的值是8，但是點(diǎn)A的值加上邊上的權(quán)重2，得到5，比點(diǎn)B的值（8）小，所以，點(diǎn)B的值減小為5。這個(gè)過(guò)程的意義是，找到了一條通向B點(diǎn)更短的路線，且該路線是先經(jīng)過(guò)點(diǎn)A，然后通過(guò)權(quán)重為2的邊，到達(dá)點(diǎn)B。
當(dāng)然，如果出現(xiàn)一下情況
則不會(huì)修改點(diǎn)B的值，因?yàn)?＋4>6。
Bellman－Ford算法可以大致分為三個(gè)部分
第一，初始化所有點(diǎn)。每一個(gè)點(diǎn)保存一個(gè)值，表示從原點(diǎn)到達(dá)這個(gè)點(diǎn)的距離，將原點(diǎn)的值設(shè)為0，其它的點(diǎn)的值設(shè)為無(wú)窮大（表示不可達(dá)）。
第二，進(jìn)行循環(huán)，循環(huán)下標(biāo)為從1到n－1（n等于圖中點(diǎn)的個(gè)數(shù)）。在循環(huán)內(nèi)部，遍歷所有的邊，進(jìn)行松弛計(jì)算。
第三，遍歷途中所有的邊（edge（u，v）），判斷是否存在這樣情況：
d（v） > d (u) + w(u,v)
則返回false，表示途中存在從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路。
之所以需要第三部分的原因，是因?yàn)?，如果存在從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路。則 應(yīng)為無(wú)法收斂而導(dǎo)致不能求出最短路徑。
考慮如下的圖：
經(jīng)過(guò)第一次遍歷后，點(diǎn)B的值變?yōu)?，點(diǎn)C的值變?yōu)?，這時(shí)，注意權(quán)重為－10的邊，這條邊的存在，導(dǎo)致點(diǎn)A的值變?yōu)椋?。（8＋ －10＝－2）
第二次遍歷后，點(diǎn)B的值變?yōu)?，點(diǎn)C變?yōu)?，點(diǎn)A變?yōu)椋?。正是因?yàn)橛幸粭l負(fù)邊在回路中，導(dǎo)致每次遍歷后，各個(gè)點(diǎn)的值不斷變小。
在回過(guò)來(lái)看一下bellman－ford算法的第三部分，遍歷所有邊，檢查是否存在d（v） > d (u) + w(u,v)。因?yàn)榈诙糠盅h(huán)的次數(shù)是定長(zhǎng)的，所以如果存在無(wú)法收斂的情況，則肯定能夠在第三部分中檢查出來(lái)。比如
此時(shí)，點(diǎn)A的值為－2，點(diǎn)B的值為5，邊AB的權(quán)重為5，5 > -2 + 5. 檢查出來(lái)這條邊沒(méi)有收斂。
所以，Bellman－Ford算法可以解決圖中有權(quán)為負(fù)數(shù)的邊的單源最短路徑問(wèn)。
個(gè)人感覺(jué)算法導(dǎo)論講解很不錯(cuò)，把這一章貼出來(lái)和大家分享:
24.1 The Bellman-Ford algorithm
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.
The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.
BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i ← 1 to |V[G]| - 1
3 do for each edge (u, v) ∈ E[G]
4 do RELAX(u, v, w)
5 for each edge (u, v) ∈ E[G]
6 do if d[v] > d[u] + w(u, v)
7 then return FALSE
8 return TRUE
Figure 24.4 shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the dand π values of all vertices in line 1, the algorithm makes |V| – 1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We’ll see a little later why this check works.)
（單擊圖片可以放大）
Figure 24.4: The execution of the Bellman-Ford algorithm. The source is vertex s. The d values are shown within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then π[v] = u. In this particular example, each pass relaxes the edges in the order (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The d and π values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example.
The Bellman-Ford algorithm runs in time O(V E), since the initialization in line 1 takes Θ(V) time, each of the |V| – 1 passes over the edges in lines 2-4 takes Θ(E) time, and the for loop of lines 5-7 takes O(E) time.
以下是Bellman-Ford代碼:
/*
* About: Bellman-Ford算法
* Author: Tanky Woo
* Blog: www.WuTianqi.com
*/
#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;
// 邊，
typedef struct Edge{
int u, v; // 起點(diǎn)，重點(diǎn)
int weight; // 邊的權(quán)值
}Edge;
Edge edge[maxnum]; // 保存邊的值
int dist[maxnum]; // 結(jié)點(diǎn)到源點(diǎn)最小距離
int nodenum, edgenum, source; // 結(jié)點(diǎn)數(shù)，邊數(shù)，源點(diǎn)
// 初始化圖
void init()
{
// 輸入結(jié)點(diǎn)數(shù)，邊數(shù)，源點(diǎn)
cin >> nodenum >> edgenum >> source;
for(int i=1; i<=nodenum; ++i)
dist[i] = maxint;
dist[source] = 0;
for(int i=1; i<=edgenum; ++i)
{
cin >> edge[i].u >> edge[i].v >> edge[i].weight;
if(edge[i].u == source) //注意這里設(shè)置初始情況
dist[edge[i].v] = edge[i].weight;
}
}
// 松弛計(jì)算
void relax(int u, int v, int weight)
{
if(dist[v] > dist[u] + weight)
dist[v] = dist[u] + weight;
}
bool Bellman_Ford()
{
for(int i=1; i<=nodenum-1; ++i)
for(int j=1; j<=edgenum; ++j)
relax(edge[j].u, edge[j].v, edge[j].weight);
bool flag = 1;
// 判斷是否有負(fù)環(huán)路
for(int i=1; i<=edgenum; ++i)
if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
{
flag = 0;
break;
}
return flag;
}
int main()
{
//freopen("input3.txt", "r", stdin);
init();
if(Bellman_Ford())
for(int i = 1 ;i <= nodenum; i++)
cout << dist[i] << endl;
return 0;
}