Dijkstra算法描述

1、Dijkstra算法描述目錄一、算法概述2二、算法原理及計算22.1算法原理22.2計算過程22.3改進的算法（Dijkstra-like）分析5三、源碼分析5四、接口調(diào)用6一、算法概述Dijkstra（迪杰斯特拉）算法是典型的單源最短路徑計算算法，用于解決源點到所有結(jié)點最短路徑計算的問題，它采用了分治和貪心（動態(tài)規(guī)劃的特殊形式）的思想搜索全局最優(yōu)解。本系統(tǒng)采用了主流、開源的JAVA圖論庫Jgrapht來解決源點到終點間所有可能路徑輸出的問題，它的核心計算引擎采用了一種Dijkstra-like算法，由經(jīng)典的Dijkstra（迪杰斯特拉）算法演化和改進而來。二、算法原理及計算2.1算法原理Di

2、jkstra算法思想為：設是帶權(quán)有向圖，代表圖中頂點集合，代表圖中含權(quán)重的邊集合。將全部頂點集合分成兩組，第一組為已求出最短路徑的頂點集合，用表示（初始時中只有一個源點，以后每求得一條最短路徑，就將該路徑的終點加入到集合中）；第二組為其余待確定最短路徑的頂點集合，用表示。按最短路徑長度的遞增次序依次把集合的頂點逐個加入到集合中，約束條件是保持從源點到中各頂點的最短路徑長度不大于從源點到中任何頂點的最短路徑長度。算法的終止條件是集合為空集，即集合的頂點全部加入到集合中。2.2計算過程以圖1為例討論Dijkstra算法的計算過程，即計算某源點到網(wǎng)絡上其余各結(jié)點的最短路徑，設源點為，逐步搜索，每次找

3、出一個結(jié)點到源點的最短路徑，直至完成所有結(jié)點的計算。圖1 帶權(quán)有向圖記為源點到某終點的距離，是源點到終點某條路徑的所有鏈路長度之和。記是源點到終點的距離。Dijkstra算法歸納如下：（1）初始化，令是已求出最短路徑的頂點集合，是其余未確定最短路徑的頂點集合，可寫出： (1-1)公式1-1中，是源點與終點的直連路徑長度，而代表源點與終點不相連,初始化結(jié)果如表1所示；（2）遍歷集合中的所有結(jié)點并計算。所有結(jié)點中尋找一個結(jié)點，用最小值去更新值，并將其從集合中剔除并加入到集合中。（3）重復步驟（2），直至集合為空集。表1 針對圖1的最短路徑計算過程步驟SUD(2)D(3)D(4)D(5)D(6)初始

4、化241124Add242231Add43Add312442Add12452312Add表1是針對圖1的詳細計算步驟的中間結(jié)果。具體計算描述如下：初始化步驟：由于初始選擇了源點，因此集合只是結(jié)點。觀察圖1，源點到結(jié)點、的直連路徑長度分別為2，4和1，到結(jié)點、不存在直連邊因而為。根據(jù)計算結(jié)果，集合所有結(jié)點的最小值為，因而將結(jié)點從集合中剔除并將其加入到集合中步驟1：針對結(jié)點，（是遍歷集合的某結(jié)點，是集合新加入結(jié)點），而，因而源點到結(jié)點的最小距離為2；針對結(jié)點，（是遍歷集合的某結(jié)點，是集合新加入結(jié)點），而，因而源點到結(jié)點的最小距離為4；針對結(jié)點，是集合新加入結(jié)點，標記為Add；針對結(jié)點，（是遍歷集合

5、的某結(jié)點，是集合新加入結(jié)點），而，因而源點到結(jié)點的最小距離為2；針對結(jié)點，（是遍歷集合的某結(jié)點，是集合新加入結(jié)點），而，因而源點到結(jié)點的最小距離為4。其余步驟同理。所有步驟演算完畢即可得出結(jié)點1的最短路徑路由信息，如圖2所示。圖2 用Dijkstra算法得出結(jié)點1的最短路徑路由表通過上述Dijkstra算法的演算步驟可發(fā)現(xiàn)，如需在全局中搜索最短路徑的全局最優(yōu)解，每個步驟必須針對其余所有結(jié)點進行一次距離的計算，以搜索出下一步可能存在的路徑。因此，Dijkstra算法的計算過程實際上提供了一個全局搜索所有可能路徑的思路。換句話說，Dijkstra算法想要尋找全局最短路徑，首先務必搜索出所有可能的路

6、徑。2.3改進的算法（Dijkstra-like）分析開源的JAVA圖論庫Jgrapht通過Dijkstra-like算法搜索全局所有可能路徑的計算方法實際上是基于經(jīng)典Dijkstra算法的完整計算流程來實現(xiàn)的。但是由于Dijkstr算法先天存在明顯的缺陷，Dijkstra-like算法對其進行了如下改進以滿足時間復雜性、空間復雜性等計算要求：（1）Dijkstra算法在通過距離計算尋找局部最優(yōu)路徑過程中，將所有可能路徑對比后，若發(fā)現(xiàn)該路徑不是局部最優(yōu)解則會將其丟棄。因此，Dijkstra-like算法在搜索所有可能路徑則需要將可能結(jié)果記錄下來并參與到下一步驟的計算；（2）Dijkstr算法處

7、理過程中，在搜索所有可能路徑時需要遍歷所有結(jié)點進行一次距離計算，哪怕是沒有直連關系且距離為的結(jié)點也參與計算，對于網(wǎng)絡拓樸圖龐大的應用場景，這將產(chǎn)生大量的計算資源浪費。因此，Dijkstra-like算法每次針對結(jié)點計算時，首先獲取該結(jié)點相連的邊，只計算有直連關系的結(jié)點從而過濾掉距離為的一類結(jié)點，大大節(jié)約計算資源。三、源碼分析public List<GraphPath<V, E>> getAllPaths( Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly,

8、Integer maxPathLength) / Decorate the edges with the minimum path lengths through them Map<E, Integer> edgeMinDistancesFromTargets = edgeMinDistancesBackwards(targetVertices, maxPathLength); / Generate all the paths List<GraphPath<V, E>> allPaths = generatePaths( sourceVertices, ta

9、rgetVertices, simplePathsOnly, maxPathLength, edgeMinDistancesFromTargets); return allPaths;edgeMinDistancesBackwards()函數(shù)傳入終點和最大搜索路徑長度，從終點開始逐步往前搜索生成網(wǎng)絡拓樸圖中所有邊距離該終點的鏈路長度，直至拓樸圖搜索完畢或者達到最大搜索長度時結(jié)束，準備進行下一步驟計算。generatePaths()函數(shù)傳入源點、終點和最大路徑長度等信息，基于上一步驟的搜索結(jié)果從源點開始逐步往后搜索到終點，直至找到該終點或者達到最大路徑長度時結(jié)束。搜索過程中保存每一條存在的路徑并將最終結(jié)果返回出來。四、接口調(diào)用List<GraphPath<V,E>> getAllPaths(Set<V> sourceVertices, Set<V> targetVertices, boolean s