[ Alg info ] Bellman–Ford algorithm (shortest path problem)

Preface: 
Bellman–Ford algorithm 是由 Richard Bellman 和 Lester Ford 創立的，求解單源最短路徑問題的一種演算法. 常見的最短路徑問題演算法還有 Dijkstra's algorithm, 且 Dijkstra 演算法不允許路徑的 cost 是負值, 但此演算法不受此限制. 但是如果圖形中有包含 cycle, 且 cycle 上面的 cost 的合為負值, 則此演算法不適合用於此種圖形. 

Description: 
在此演算法中, 最外面的 loop 是 path 的長度, 也就是理想下最多走 |V|-1 步應該可以到達終點 (不考慮有 loop 的情況下). 接著在外層 loop 裡再 loop 整個 Graph 的 edge(u,v), 並使用distance[destination vertex] 矩陣紀錄從 source vertex 到 destination vertex 走 n-1 步能到的最短的路徑 (目前要計算第 n 步能走到的最短距離). 並用下面的式子決定要不要更新矩陣distance[destination vertex]: 

view plaincopy to clipboardprint?

1. for i from 1 to size(vertices)-1:  
2.        for each edge (u, v) with weight w in edges:  
3.            if distance[u] + w < distance[v]:  
4.                distance[v] := distance[u] + w  
5.                predecessor[v] := u  

其中判斷式 distance[u] + w < distance[v] 說明如果 (走 n-1 步能到 vertex u 的距離加上由 vertex u 走到 vertex v 所需要的 cost=w) 小於 distance[v] (走 n-1 步能到達 vertex v 的最短距離), 則將走 n 步能到達 vertex v 的值設為 distance[v] := distance[u] + w 

Bellman–Ford algorithm: 
整個演算法的 pseudo code 如下: 

view plaincopy to clipboardprint?

1. procedure BellmanFord(list vertices, list edges, vertex source)  
2.    // This implementation takes in a graph, represented as lists of vertices and edges,  
3.    // and fills two arrays (distance and predecessor) with shortest-path information  
4.   
5.    // Step 1: initialize graph  
6.    for each vertex v in vertices:  
7.        if v is source then distance[v] := 0  
8.        else distance[v] := infinity  
9.        predecessor[v] := null  
10.   
11.    // Step 2: relax edges repeatedly  
12.    for i from 1 to size(vertices)-1:  
13.        for each edge (u, v) with weight w in edges:  
14.            if distance[u] + w < distance[v]:  
15.                distance[v] := distance[u] + w  
16.                predecessor[v] := u  
17.   
18.    // Step 3: check for negative-weight cycles  
19.    for each edge (u, v) with weight w in edges:  
20.        if distance[u] + w < distance[v]:  
21.            error "Graph contains a negative-weight cycle"  

上面的 Step1 是在初始化讓 source vertex 到其他每個 destination vertex 的距離為 infinity; 接著 Step2 就是在進行上面 description 說明的動作, 從走一步, 二步 ... 一直到 |V|-1 步找出每個階段下能走到各個 destination vertex 所需的最短路徑; 最後 Step3 是在找出是否有 cycle 請該 cycle 的 cost 合為負值, 此時該 Graph 便不適合此演算法. 

Example: 
下面圖形共有 7 個 vertex, 說明最外面的 loop 只需要跑 7-1=6 次, 接下來我們要示範從 vertex 0 使用 Bellman-Ford 演算法找出到各個其他 vertex 的最短距離: 
Loop1: 從 vertex 0 走一步能到達的只有 vertex 1,2,3: 

distance[1]=infinity > distance[0]+edge(0,1) = 6 , 故更新 distance[1]=6
distance[2]=infinity > distance[0]+edge(0,2) = 5 , 故更新 distance[2]=5 
...

 
Loop2: 從上一次結果發現只有 vertex 1,2,3 的 distance 矩陣的值不為 infinity, 故檢查這些 vertex 的 out edge: 

distance[1]=6 < distance[2] + edge(2,1)=5+(-2)=3, 故更新 distance[1]=3
...

 
Loop3: 從上一次結果發現, 有 vertex 1,2,3,4,5 的 distance 矩陣的值不為 infinity, 故檢查這些 vertex 的 out edge: 

distance[1]=3 < distance[2] + edge(2,1)=3+(-2)=1, 故更新 distance[1]=1
...

 
Loop4: 從上一次結果發現, 所有 vertex 的 distance 矩陣的值都不為 infinity: 

distance[4]=2 < distance[1] + edge(1,4)=1+(-1)=0, 故更新 distance[4]=0
...

 
Loop5-6: 在 loop5~6 沒有找到從 vertex 0 到其他 vertex 更短的路徑. 6=|V|-1, 故結束此演算法: 
 

Implement: 
- map.alg.SPP.java 

view plaincopy to clipboardprint?

1. public static HashMap> Bellman_Ford(Graph g, Vertex s)  
2. {  
3.     return Bellman_Ford(g, s, g.vtxMap.size()-1);  
4. }  
5.   
6. public static HashMap> Bellman_Ford(Graph g, Vertex s, int iter)  
7. {  
8.     HashMap> edgeMap = new HashMap>();  
9.     // Step 1: initialize graph    
10.     for(Vertex v:g.vtxMap.values())  
11.     {  
12.         if(v.equals(s))  {  
13.             edgeMap.put(v.name, null); // Source vertex doesn't have to calculate SP.                 
14.         }  
15.         else edgeMap.put(v.name, new ArrayList());  
16.     }  
17.       
18.     // Step 2: relax edges repeatedly   
19.     Set availVtxSet = new HashSet();  
20.     List addEdgeList = new ArrayList();  
21.     availVtxSet.add(s);  
22.     for(int i=1; i<=iter; i++) // Path count 1~(n-1)  
23.     {  
24.         System.out.printf("\t[Info] Iter%d:\n", i);           
25.         for(Vertex t:g.vtxMap.values()) // Pickup destination vertex  
26.         {  
27.             Edge te = null;  
28.             Vertex mv = null;  
29.             List edgeList = edgeMap.get(t.name);  
30.             if(edgeList==null) {  
31.                 //Skip destination vertex = source vertex.  
32.                 continue;  
33.             }  
34.             int c = BellmanLC(edgeList);          
35.             for(Vertex v:availVtxSet)  
36.             {  
37.                 int vc = BellmanLC(edgeMap.get(v.name));   
38.                 if(vc==INFINITE) continue;  
39.                 for(Edge e:v.edgeSet)  
40.                 {  
41.                     if(e.to.equals(t))  
42.                     {  
43.                         if(vc+e.cost
44.                         {  
45.                             te = e;  
46.                             c = vc + e.cost;  
47.                             mv = v;  
48.                         }                                 
49.                         break;  
50.                     }  
51.                 }  
52.             }  
53.             if(te!=null) {  
54.                 edgeList.clear();  
55.                 List middleList = edgeMap.get(mv.name);  
56.                 if(middleList!=null) edgeList.addAll(middleList);  
57.                 edgeList.add(te);  
58.                 addEdgeList.add(te.to);  
59.                 System.out.printf("\tAdd edge=%s: %d\n", te, BellmanLC(edgeList));  
60.             }  
61.         }  
62.         availVtxSet.addAll(addEdgeList);  
63.         addEdgeList.clear();  
64.     }  
65.       
66.     // Step 3: check for negative-weight cycles  
67.     for(Vertex v:g.vtxMap.values())  
68.     {  
69.         for(Edge e:v.edgeSet)  
70.         {  
71.             int su = BellmanLC(edgeMap.get(e.from.name));  
72.             int tu = BellmanLC(edgeMap.get(e.to.name));  
73.             if(su+e.cost
74.                 System.err.printf("\t[Warn] Not proper graph for Bellman-Ford!\n");  
75.                 System.out.printf("\t[Warn] Edge=%s (%d-%d->%d)\n", e, su, e.cost, tu);  
76.                 return null;  
77.             }  
78.         }  
79.     }  
80.       
81.     return edgeMap;  
82. }  

執行結果: 

[Info] SPP from 0 to 3 = 5
0->3 (5)
[Info] SPP from 0 to 2 = 3
0->3 (5), 3->2 (-2)
[Info] SPP from 0 to 1 = 1
0->3 (5), 3->2 (-2), 2->1 (-2)
[Info] SPP from 0 to 0 = 0
[Info] SPP from 0 to 6 = 3
0->3 (5), 3->2 (-2), 2->1 (-2), 1->4 (-1), 4->6 (3)
[Info] SPP from 0 to 5 = 4
0->3 (5), 3->5 (-1)
[Info] SPP from 0 to 4 = 0
0->3 (5), 3->2 (-2), 2->1 (-2), 1->4 (-1)

完整代碼可以在 這裡 下載! 

Spplement: 
* Single Source Shortest Paths: Label Correcting Algorithm（Bellman-Ford Algorithm） 
* Graph Theory Applet 
* [CSIE 1212] Data Structure and Algorithm - 4/30 Graph3