[ Java 代碼範本 ] JGraphT - Shortest Path (ST)

Introduction 
在一個有向圖形 G=(V,E), G 中的每一個邊都有一個比例常數 W(Weight) 與之對應, 如果想求 G 圖形中某一點V0 到其他頂點的最少 W 總和之值, 這類問題就稱為最短路徑問題 (The shortest path problem). 通常在解決問題的同時, 不同的演算法可以解的範圍也不一樣: 

* 單點對單點 (Source Sink)
* 單點對多點 (Single Source)
* 多點對多點 (All Pairs)

不同的演算法對於 Graph 的要求也不盡相同, 底下是常見的 Restriction: 

* 只能接受非負數的 Weighting (Nonnegative weights)
* 使用 Euclidean weights.
* 可接受 Arbitrary weights.
* 不能有 Cycle 的產生 (No directed cycles.)

底下我們要來看幾個常見的 Shortest Path 演算法, 並使用 JGraphT 來實作. 

MST Algorithm 
在開始介紹 SP 演算法類別前, 我們先使用 SimpleDirectedWeightedGraph 類別建立我們的範例 Graph: 

view plaincopy to clipboardprint?

1. package graph.alg  
2.   
3. import org.jgrapht.graph.DefaultWeightedEdge  
4. import org.jgrapht.graph.SimpleDirectedWeightedGraph  
5.   
6. // 0) Initialize Graph    
7. SimpleDirectedWeightedGraph g =    
8.             new SimpleDirectedWeightedGraph(DefaultWeightedEdge.class)  
9.   
10. // 1) Build Graph  
11. 6.times{  
12.     g.addVertex(it)  
13. }  
14.   
15. def edges = [:]  
16. edges[0]=[1:8]  
17. edges[1]=[2: 6,4:16]  
18. edges[2]=[3:10,5:15]  
19. edges[4]=[0:12]  
20. edges[5]=[1:12,4:14]  
21.   
22. edges.each{ k, v->  
23.     v.each{ n, w->  
24.         DefaultWeightedEdge e = g.addEdge(k, n)  
25.         if(e!=null)  
26.         {  
27.             g.setEdgeWeight(e, w)  
28.         }  
29.     }  
30. }  

其圖形長相如下: 
 

- Dijkstra's Algorithm (DijkstraShortestPath) 
一個頂點到多個頂點通常使用 Dijkstra 演算法 求得, 有關 Dijkstra 的演算法可以參考 這裡. 

範例代碼如下: 

view plaincopy to clipboardprint?

1. // 2) Algorithm  
2. printf("\t[Info] Running Dijkstra Shortest Path:\n")  
3. (1..5).each { d->  
4.     DijkstraShortestPath dijkstraSP = new DijkstraShortestPath(g, 0, d)  
5.     printf("\t0->%d (%.01f):\t", d, dijkstraSP.getPathLength())        
6.     for(DefaultWeightedEdge e:dijkstraSP.getPathEdgeList()) printf("%s ", e)  
7.     println()  
8. }  

執行結果: 

[Info] Running Dijkstra Shortest Path:
0->1 (8.0): (0 : 1)
0->2 (14.0): (0 : 1) (1 : 2)
0->3 (24.0): (0 : 1) (1 : 2) (2 : 3)
0->4 (24.0): (0 : 1) (1 : 4)
0->5 (29.0): (0 : 1) (1 : 2) (2 : 5)

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

範例代碼如下: 

view plaincopy to clipboardprint?

1. // 2) Algorithm  
2. printf("\t[Info] Running Bellman-Ford Shortest Path:\n")  
3. BellmanFordShortestPath bfSP = new BellmanFordShortestPath(g, 0)  
4. (1..5).each { d->  
5.     printf("\t0->%d (%.01f):\t", d, bfSP.getCost(d))  
6.     for(DefaultWeightedEdge e:bfSP.getPathEdgeList(d)) printf("%s ", e)  
7.     println()  
8. }  

執行結果: 

[Info] Running Bellman-Ford Shortest Path:
0->1 (8.0): (0 : 1)
0->2 (14.0): (0 : 1) (1 : 2)
0->3 (24.0): (0 : 1) (1 : 2) (2 : 3)
0->4 (24.0): (0 : 1) (1 : 4)
0->5 (29.0): (0 : 1) (1 : 2) (2 : 5)

- Floyd–Warshall algorithm (FloydWarshallShortestPaths) 
Floyd-Warshall 算法 可以用來計算 All-pairs Shortest Path 問題. 

範例代碼如下: 

view plaincopy to clipboardprint?

1. // 2) Algorithm  
2. printf("\t[Info] Running Floyd-Warshall Algorithm:\n")  
3. FloydWarshallShortestPaths fwSP = new FloydWarshallShortestPaths(g)  
4.   
5. (1..5).each { d->  
6.     printf("\t0->%d (%.01f):\t", d, fwSP.shortestDistance(0, d))  
7.     for(DefaultWeightedEdge e:fwSP.getShortestPath(0, d).getEdgeList()) printf("%s ", e)  
8.     println()  
9. }  

執行結果: 

[Info] Running Floyd-Warshall Algorithm:
0->1 (8.0): (0 : 1)
0->2 (14.0): (0 : 1) (1 : 2)
0->3 (24.0): (0 : 1) (1 : 2) (2 : 3)
0->4 (24.0): (0 : 1) (1 : 4)
0->5 (29.0): (0 : 1) (1 : 2) (2 : 5)

Supplement 
* 圖形結構 : 圖形最短路徑 (單點對全部頂點) 
* Section 25.5 : Dijkstra's Minimum-Path Algorithm 
* Coursera - Algorithms, Part II - Completed Dijkstra's Algorithm (18:58) 
* Coursera - Algorithms, Part II - Bellman-Ford Algorithm 
* [ Alg info ] Bellman–Ford algorithm (shortest path problem) 
* [ Alg info ] Dijkstra’s algorithm (shortest path problem)