圖論基礎之Dijkstra演算法的初探

圖論， 顧名思義就是有圖有論。

圖：由點“Vertex”和邊“Edge ”組成， 且圖分為有向圖和無向圖(本文討論有向圖)， 之前做畢業設計的時候研究“多譜流形聚類演算法”的時候有研究“Graph”。 高維資料的聚類就涉及到Graph Cut演算法， 想像資料為歐式空間的點， 資料與資料之間呈現這樣或那樣的聯繫， 資料就是點， 他們的聯繫由邊來決定。 PS：本次學習與聚類演算法無關， 聚類問題具體見之前寫的博客。

論：構建好了目標物件以及目標物件的關係， 接下來的大頭與研究的目的有關。 比如， 圖論最廣泛的應用之一：社交網路。 我與張三是好朋友，

那麼我跟張三之間就有一個Edge來表示我倆之間的聯繫， 張三與李四是好朋友， 那張三和李四之間也有一個Edge來連接。 如果我和李四之間沒關係， 那麼我要想聯繫李四就需要通過聯繫張三再通過張三來和李四產生聯繫。 一來二往， 我和李四熟了， 這時候我跟李四之間也有了Edge， 這個時候我聯繫李四的方式就不止一種了， 比如我既可以通過張三聯繫李四， 也可以直接聯繫李四， 至於選擇哪種聯繫方式， 而這個選擇的過程中就涉及到你和張三的關係好壞程度、你與李四的好壞程度以及李四和張三的好壞程度， 這種好壞程度在Graph中一般稱為“權重”， 權值為正關係好， 權值為負關係差， 再言之， 關係這種東西是以自我為中心， 比如我認為我和張三的關係是很好， 但張三不認為我跟他的關係很好， 這裡就涉及到“有向圖”。 而今天討論的“論”的目標為最短路徑問題。

解決最短路徑問題的方法有很多種， 本文主要探討Dijkstra最短路徑演算法， 通過闡述演算法過程， 實現簡單Dijkstra演算法， 來對最短路徑問題有一個比較深刻的瞭解。 其次， 我們知道JAVA作為物件導向的高階語言， 有很多的輪子， 我在穀歌搜了半天發現文檔比較友好且演算法和視覺化都比較良好的開源輪子， 分別是：JGraphT和GraphStream， 這裡只討論JGraphT的調用（因為這個輪子的說明文檔很nice ^$^）。

Dijkstra演算法流程

初始化：稱給定的初始節點為根節點， 給每一個節點設置設定初始化的距離（距離根節點）， 其中， 根節點的距離為0（與自身的距離當然是0）， 其他所有節點與根節點的距離都是無窮大（不同場景下的距離可取不同的值， 如電腦中一般取整型的最大值）；創建兩個集合， 一個集合用於收集已訪問節點， 另外一個集合收集待訪問節點。 迴圈：對當前節點， 重新計算根節點與所有鄰接點的暫時距離， 將這個新計算的暫時距離與鄰接節點的當前距離進行比較取這兩個距離中較小的值去更新鄰接點的距離。 比如當前節點為A,A有一個鄰接點B， 其中根節點為O；若A的當前距離為W(O,A)=6， B的當前距離為W(O,B)=10， A與其鄰接點B的距離為distance(A,B)=2。 則因為根節點O與A的鄰接點B的暫時距離distance(O,B)等於W(O,A)+W(A,B)=6+2=8<><>

這裡， 我並不貼大量代碼演示演算法流程， 只是做一個對比， 討論一下Dijkstra演算法中的演算法複雜度的提升上這麼一個漸進的過程。

下圖圖1來自於維琪百科的引用：

圖1 各最短路徑演算法的提出

上圖1中紅框標注的三種Dijkstra演算法， 第一種方法是使用清單反覆運算的方式來求的最小距離， 部分代碼如下：

for (index = 1; index CostTime[index]) { Vertex = index; MinTime = CostTime[index]; } }

以上是C++實現， 上面的代碼中尋找鄰節點最短距離以及對應的節點， 直接遍歷所有未被訪問的節點， 時間複雜度為 O(V^2)， 而後面提出的“優先佇列”， 在JAVA中為PriorityQueue， 實際上就是一個堆的實現， 這個佇列存儲當前節點的鄰近點資訊， 並將鄰近點的距離進行排序， 最小的距離排在最前面， 方便取出， 具體實現如下：

//可獲取節點的排序實現 this.availableVertices = new PriorityQueue(vertexKeys.size, new Comparator { @Override public int compare(Vertex one, Vertex two) { int weightOne = Dijkstra.this.distances.get(one.getLabel); int weightTwo = Dijkstra.this.distances.get(two.getLabel); return weightOne - weightTwo; } }); //查找最短距離的節點更新節點的最短距離 while (this.availableVertices.size > 0) { //Pick the closest vertex Vertex next = this.availableVertices.poll; int distanceToNext = this.distances.get(next.getLabel); //便利當前節點的所有鄰節點 List nextNeighbors = next.getNeighbors; for(Edge e: nextNeighbors){ Vertex other = e.getNeighbor(next); if(this.visitedVertices.contains(other)){ continue; } //更新距離 int currentWeight = this.distances.get(other.getLabel); int newWeight = distanceToNext + e.getWeight; if(newWeight

以後從這個PriorityQueue中依次存取當前節點的鄰接節點。

比如poll出頭元素即為距離最短的節點替代為下一次迴圈的當前節點， 後面再訪問鄰接點並往這個佇列添加元素， 省去了創建一個新的待訪問集合的步驟。

第二種和第三者優先佇列， 分別是二叉樹堆（Binary_heap）和斐波那契堆（Fibonacci_heap）， 其實， 這些都屬於樹的搜索演算法， 我們常用的一般都是二叉樹， 例如PriorityQueue的實現就是二叉樹最小堆的一個介面， 具體情況可以看一下這個博客對源碼的解析。

接下， 演示一下強大的JGraphT的實現Dijkstra演算法：

package cn.probabilityModel.graphPkg; import java.util.HashMap; import java.util.List; import cn.ODBackModel.utils.NoNameExUtil; import cn.probabilityModel.xmlPkg.XmlParse; import org.jgrapht.alg.interfaces.ShortestPathAlgorithm; import org.jgrapht.alg.shortestpath.DijkstraShortestPath; import org.jgrapht.graph.*; /** * 使用JGraphT求最短距離， 注意JGraphT中的Dijkstra中的最短距離由斐波那契搜索到 * Create the shortest path according to the shortestPath's algorithm * Created by wing1995 on 2017/6/28. */ public class ShortestPath { public static void main(String args[]) { //構建一個加權有向圖 SimpleDirectedWeightedGraph metroGraph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class); List> stationConnectInfor = XmlParse.getStationConnectInfor; //獲取資料 //創建邊和點以及權重 for(HashMap stationInfo: stationConnectInfor){ String fromStation = NoNameExUtil.NO2Name(stationInfo.get("StatNo")); String toStation = NoNameExUtil.NO2Name(stationInfo.get("NextStatNo")); Double costTime = Double.parseDouble(stationInfo.get("RunningTime2")); metroGraph.addVertex(fromStation); if (toStation != null) { metroGraph.addVertex(toStation); DefaultWeightedEdge metroEdge = metroGraph.addEdge(fromStation, toStation); metroGraph.setEdgeWeight(metroEdge, costTime); } } // 列印從機場東到寶安中心的路徑（都在一條線路） System.out.println("從機場東到寶安中心的最短路徑:"); DijkstraShortestPath dijkstraAlg = new DijkstraShortestPath<>(metroGraph); ShortestPathAlgorithm.SingleSourcePaths iPaths = dijkstraAlg.getPaths("機場東"); System.out.println(iPaths.getPath("寶安中心") + " "); // 列印從機場東到翻身的路徑（不同地鐵線路的兩個網站） System.out.println("從寶安中心到寶華:"); ShortestPathAlgorithm.SingleSourcePaths cPaths = dijkstraAlg.getPaths("寶安中心"); System.out.println(cPaths.getPath("寶華")); } }

速度杠杠滴！

結果如下：

注意，上面寶安中心到寶華的最短路徑實際上，寶安中心可以直達寶華，之所以走了寶安中心道新安的方向找最短路徑，是因為，我提供的資料中只創建了一個方向，也就是沒有創建寶安中心沿著寶華方向的有向圖。

結果如下：

注意，上面寶安中心到寶華的最短路徑實際上，寶安中心可以直達寶華，之所以走了寶安中心道新安的方向找最短路徑，是因為，我提供的資料中只創建了一個方向，也就是沒有創建寶安中心沿著寶華方向的有向圖。