## 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:

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

Bellman–Ford algorithm:

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"

Example:

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();
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);
59.                 System.out.printf("\tAdd edge=%s: %d\n", te, BellmanLC(edgeList));
60.             }
61.         }
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

### [ Python 常見問題 ] python generator “send” function purpose?

Source From  Here   Question   Can someone give me an example of why the "send" function associated with Python generator function...