程式扎記: [ Java 代碼範本 ] JGraphT - Shortest Path (ST)

標籤

2015年11月8日 星期日

[ 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: 
  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]=[26,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 的演算法可以參考 這裡



範例代碼如下: 

  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 的合為負值, 則此演算法不適合用於此種圖形. 



範例代碼如下: 

  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 問題. 



範例代碼如下: 

  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)

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!