相關文章：
1.Dijkstra算法：
http://www.wutianqi.com/?p=1890
2.Floyd算法：
http://www.wutianqi.com/?p=1903
Dijkstra算法是處理單源最短路徑的有效算法，但它局限于邊的權值非負的情況，若圖中出現(xiàn)權值為負的邊，Dijkstra算法就會失效，求出的最短路徑就可能是錯的。這時候，就需要使用其他的算法來求解最短路徑，Bellman-Ford算法就是其中最常用的一個。該算法由美國數(shù)學家理查德•貝爾曼（Richard Bellman, 動態(tài)規(guī)劃的提出者）和小萊斯特•福特（Lester Ford）發(fā)明。Bellman-Ford算法的流程如下：
給定圖G(V, E)（其中V、E分別為圖G的頂點集與邊集），源點s，
- 數(shù)組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數(shù)組Distant[n]為, Distant[s]為0；
-
以下操作循環(huán)執(zhí)行至多n-1次，n為頂點數(shù)：
對于每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；
若上述操作沒有對Distant進行更新，說明最短路徑已經(jīng)查找完畢，或者部分點不可達，跳出循環(huán)。否則執(zhí)行下次循環(huán)；
- 為了檢測圖中是否存在負環(huán)路，即權值之和小于0的環(huán)路。對于每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環(huán)路，即是說改圖無法求出單源最短路徑。否則數(shù)組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。
可知，Bellman-Ford算法尋找單源最短路徑的時間復雜度為O(V*E).
首先介紹一下松弛計算。如下圖：
松弛計算之前，點B的值是8，但是點A的值加上邊上的權重2，得到5，比點B的值（8）小，所以，點B的值減小為5。這個過程的意義是，找到了一條通向B點更短的路線，且該路線是先經(jīng)過點A，然后通過權重為2的邊，到達點B。
當然，如果出現(xiàn)一下情況
則不會修改點B的值，因為3＋4>6。
Bellman－Ford算法可以大致分為三個部分
第一，初始化所有點。每一個點保存一個值，表示從原點到達這個點的距離，將原點的值設為0，其它的點的值設為無窮大（表示不可達）。
第二，進行循環(huán)，循環(huán)下標為從1到n－1（n等于圖中點的個數(shù)）。在循環(huán)內部，遍歷所有的邊，進行松弛計算。
第三，遍歷途中所有的邊（edge（u，v）），判斷是否存在這樣情況：
d（v） > d (u) + w(u,v)
則返回false，表示途中存在從源點可達的權為負的回路。
之所以需要第三部分的原因，是因為，如果存在從源點可達的權為負的回路。則 應為無法收斂而導致不能求出最短路徑。
考慮如下的圖：
經(jīng)過第一次遍歷后，點B的值變?yōu)?，點C的值變?yōu)?，這時，注意權重為－10的邊，這條邊的存在，導致點A的值變?yōu)椋?。（8＋ －10＝－2）
第二次遍歷后，點B的值變?yōu)?，點C變?yōu)?，點A變?yōu)椋?。正是因為有一條負邊在回路中，導致每次遍歷后，各個點的值不斷變小。
在回過來看一下bellman－ford算法的第三部分，遍歷所有邊，檢查是否存在d（v） > d (u) + w(u,v)。因為第二部分循環(huán)的次數(shù)是定長的，所以如果存在無法收斂的情況，則肯定能夠在第三部分中檢查出來。比如
此時，點A的值為－2，點B的值為5，邊AB的權重為5，5 > -2 + 5. 檢查出來這條邊沒有收斂。
所以，Bellman－Ford算法可以解決圖中有權為負數(shù)的邊的單源最短路徑問。
個人感覺算法導論講解很不錯，把這一章貼出來和大家分享:
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; // 起點，重點
int weight; // 邊的權值
}Edge;
Edge edge[maxnum]; // 保存邊的值
int dist[maxnum]; // 結點到源點最小距離
int nodenum, edgenum, source; // 結點數(shù)，邊數(shù)，源點
// 初始化圖
void init()
{
// 輸入結點數(shù)，邊數(shù)，源點
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) //注意這里設置初始情況
dist[edge[i].v] = edge[i].weight;
}
}
// 松弛計算
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;
// 判斷是否有負環(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;
}