2013年5月9日 星期四

[ 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]
  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 如下: 
  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 
  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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...