概述
Bellman Ford算法可以用來解決加權(quán)圖中的最短路徑問題。其與Dijkstra算法的區(qū)別在于Belllman Ford算法的應用范圍更廣，例如其可以用來處理帶有負權(quán)重的加權(quán)圖中的最短路徑問題。由于Dijkstra算法本質(zhì)上是一種貪心算法，因而當圖中存在路徑權(quán)值之和為負的環(huán)時，Dijkstra算法會給出錯誤的結(jié)果因為其總是偏向于選擇當前情況下的局部最優(yōu)路徑。Bellman Ford算法的時間復雜度高于Dijkstra算法。
歷史
Bellman Ford算法最初于1955年被Alfonso Shimbel提出，但最終基于1958和1956年發(fā)表論文的 Richard Bellman和Lester Ford, Jr.二人命名。Edward F. Moore于1957年也提出了該算法，因此該算法有時也稱作是Bellman Ford Moore算法。
負權(quán)重帶環(huán)圖的問題
包含負權(quán)重的圖在不少實際問題中有所應用。例如在尋找化學反應鏈中需要最少能量的路徑中，該反應鏈可能既包含吸熱反應也包含放熱反應，那么我們可以認為放熱反應是負權(quán)重路徑而吸熱反應是正權(quán)重路徑。在包含負權(quán)重帶環(huán)圖的問題中，從起始點開始的一條路徑如果能夠到達一個整體權(quán)重之和為負的環(huán)，則最短路徑在中情況下將不存在，因為這一路徑總可以通過在負權(quán)重路徑中循環(huán)來不斷降低總權(quán)重。而使用Bellman Ford算法則能夠發(fā)現(xiàn)這一問題。
算法描述
簡單來說，類似于Dijkstra算法，Bellman Ford算法首先將從源結(jié)點到達剩余所有結(jié)點的距離初始化為無窮大，而從源結(jié)點到其本身的距離則初始化為0。然后算法將循環(huán)檢查圖中的每一條邊。如果這條邊能夠縮短從源結(jié)點到某一目的結(jié)點的距離，則新的最短距離將被記錄下來。具體來說，對于一條邊u -> v，設(shè)其權(quán)重為weight(u, v)，而結(jié)點u，v距離源結(jié)點src的距離分別為dist[u]，dist[v]。則dist[v] = min(dist[v], dist[u] + weight(u,v)。在每一次循環(huán)中該算法都檢查所有的邊。對于第i次循環(huán)，算法將得到從源結(jié)點出發(fā)不超過i步能夠到達的結(jié)點的最短距離（在某些情況下也可能多于i）。因為對于N個結(jié)點的圖來說，不包含環(huán)的最短距離最長為N-1，所以該算法需要循環(huán)檢查所有邊N-1次。
在循環(huán)結(jié)束后，算法將再多循環(huán)檢查一遍所有的邊并嘗試更新最短路徑。如果從源結(jié)點出發(fā)到某一點的最短距離在這一次循環(huán)中能夠被更新，則說明在這一路徑上至少存在一個權(quán)重之和為負的環(huán)。
算法的Java實現(xiàn)
public class BellmanFord {
/**
* Find the shortest path from src to all other nodes in the graph
* represented using an array of arrays of shape [u, v, weight],
* in which u and v are the start and end point of the edge, respectively.
* @param n Number of nodes in the graph.
* @return An array containing the shortest path from src to all other
* nodes in the graph, with the predecessor of the nodes. For each node i, the
* array contains a two-tuple [distance, predecessor].
* If a shortest path from src to node does not exist, distance and predecessor will
* both be Integer.MAX_VALUE.
*/
public int[][] findShortestPath(int src, int n, int[][] edges) {
// first step, initialize the distance
int[] dist = new int[n];
int[] pre = new int[n];
int INF = Integer.MAX_VALUE / 2;
Arrays.fill(dist, INF);
dist[src] = 0;
Arrays.fill(pre, Integer.MAX_VALUE);
// second step, compute shortest path with at most n-1 steps
for (int i = 1; i < n; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], weight = edge[2];
if (dist[v] > dist[u] + weight) {
pre[v] = u;
}
dist[v] = Math.min(dist[v], dist[u] + weight);
}
}
// third step, check the existance of negative weight cycle
for (int[] edge : edges) {
int u = edge[0], v = edge[1], weight = edge[2];
if (dist[u] < INF && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
}
}
int[][] ret = new int[n][2];
for (int i = 0; i < n; i++) {
ret[i] = new int[]{dist[i] == INF ? Integer.MAX_VALUE : dist[i], pre[i]};
}
return ret;
}
}
時間復雜度
從上面代碼中我們可以看出我們在每一次循環(huán)中都會檢查所有的邊，共計循環(huán)了N次，那么算法的時間復雜度為O(N * E)，其中N為圖中的結(jié)點總數(shù)，E為圖中的邊的數(shù)目。
空間復雜度
O(N)。因為我們使用了O(N)大小的數(shù)組來存儲最短路徑的距離。
潛在優(yōu)化
對于step 2，如果在某一次循環(huán)中我們沒有更新任何最短距離，則這一循環(huán)可以提前結(jié)束。因為這證明該算法已經(jīng)找到了從源結(jié)點出發(fā)能夠到達的所有結(jié)點的最短路徑。這一優(yōu)化使得step 2的循環(huán)次數(shù)能夠少于O(N-1)。
