Dijkstra算法描述

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

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

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

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

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

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

7、理過程中，在搜索所有可能路徑時(shí)需要遍歷所有結(jié)點(diǎn)進(jìn)行一次距離計(jì)算，哪怕是沒有直連關(guān)系且距離為的結(jié)點(diǎn)也參與計(jì)算，對(duì)于網(wǎng)絡(luò)拓樸圖龐大的應(yīng)用場(chǎng)景，這將產(chǎn)生大量的計(jì)算資源浪費(fèi)。因此，Dijkstra-like算法每次針對(duì)結(jié)點(diǎn)計(jì)算時(shí)，首先獲取該結(jié)點(diǎn)相連的邊，只計(jì)算有直連關(guān)系的結(jié)點(diǎn)從而過濾掉距離為的一類結(jié)點(diǎn)，大大節(jié)約計(jì)算資源。三、源碼分析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ù)傳入終點(diǎn)和最大搜索路徑長(zhǎng)度，從終點(diǎn)開始逐步往前搜索生成網(wǎng)絡(luò)拓樸圖中所有邊距離該終點(diǎn)的鏈路長(zhǎng)度，直至拓樸圖搜索完畢或者達(dá)到最大搜索長(zhǎng)度時(shí)結(jié)束，準(zhǔn)備進(jìn)行下一步驟計(jì)算。generatePaths()函數(shù)傳入源點(diǎn)、終點(diǎn)和最大路徑長(zhǎng)度等信息，基于上一步驟的搜索結(jié)果從源點(diǎn)開始逐步往后搜索到終點(diǎn)，直至找到該終點(diǎn)或者達(dá)到最大路徑長(zhǎng)度時(shí)結(jié)束。搜索過程中保存每一條存在的路徑并將最終結(jié)果返回出來。四、接口調(diào)用List<GraphPath<V,E>> getAllPaths(Set<V> sourceVertices, Set<V> targetVertices, boolean s