Dijkstra算法描述

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

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

3、短路徑，設(shè)源點(diǎn)為，逐步搜索，每次找出一個(gè)結(jié)點(diǎn)到源點(diǎn)的最短路徑,直至完成所有結(jié)點(diǎn)的計(jì)算。圖1帶權(quán)有向圖記D(v)為源點(diǎn)到某終點(diǎn)v的距離，是源點(diǎn)到終點(diǎn)v某條路徑的所有鏈路長(zhǎng)度之和。記l(w,v)是源點(diǎn)w到終點(diǎn)v的距離。Dijkstra算法歸納如下：1初始化，令S是已求出最短路徑的頂點(diǎn)集合，S，U是其余未確定最短路徑的頂點(diǎn)集合，U，可寫(xiě)出：(1-1)l(1,v)公式1-1中，l(1,v)是源點(diǎn)與終點(diǎn)V的直連路徑長(zhǎng)度，而代表源點(diǎn)與終點(diǎn)V不相連，初始化結(jié)果如表1所示；2遍歷集合U中的所有結(jié)點(diǎn)v并計(jì)算minD(v),D(w)l(w,v)。所有結(jié)點(diǎn)中尋找一個(gè)結(jié)點(diǎn)w,用最小值minD(v),D(w)l(w,v

4、)去更新D(v)值，并將其從集合U中剔除并參加到集合S中。3重復(fù)步驟2，直至集合U為空集。表1針對(duì)圖1的最短路徑計(jì)算過(guò)程步驟SUD(2)D(3)D(4)D(5)D(6)初始化24188124Add242231Add43Add312442Add12452312Add表1是針對(duì)圖1的詳細(xì)計(jì)算步驟的中間結(jié)果。具體計(jì)算描述如下：初始化步驟：由于初始選擇了源點(diǎn)，因此集合S只是結(jié)點(diǎn)。觀察圖1,源點(diǎn)到結(jié)點(diǎn)、的直連路徑長(zhǎng)度分別為2,4和1,到結(jié)點(diǎn)、不存在直連邊因而為。根據(jù)計(jì)算結(jié)果，集合U所有2點(diǎn)D(w)的最小值為D(4),因而將結(jié)點(diǎn)從集合U中剔除并將其參加到集合S中步驟1：針對(duì)結(jié)點(diǎn)，v2,w4V是遍歷集合U的

5、某結(jié)點(diǎn)，W是集合S新參加結(jié)點(diǎn)，D(v)D(2)2，而D(w)l(w,v)D(4)l(4,2)123D(2)，因而源點(diǎn)到結(jié)點(diǎn)的最小距離minD(v),D(w)l(w,v)為2；針對(duì)結(jié)點(diǎn)，v3,w4V是遍歷集合U的某結(jié)點(diǎn)，w是集合S新參加結(jié)點(diǎn)，D(v)D(3)4，而D(w)l(w,v)D(4)l(4,3)1D(3)，因而源點(diǎn)到結(jié)點(diǎn)的最小距離minD(v),D(w)l(w,v)為4；針對(duì)結(jié)點(diǎn)，是集合S新參加結(jié)點(diǎn)，標(biāo)記為Add;針對(duì)結(jié)點(diǎn)，v5,w4v是遍歷集合U的某結(jié)點(diǎn)，w是集合S新參加結(jié)點(diǎn)，D(v)D(5)，而D(w)l(w,v)D(4)l(4,5)112D(5)，因而源點(diǎn)到結(jié)點(diǎn)的最小距離minD(

6、v),D(w)l(w,v)為2；針對(duì)結(jié)點(diǎn)，v6,w4v是遍歷集合U的某結(jié)點(diǎn)，w是集合S新參加結(jié)點(diǎn)，D(v)D(6)，而D(w)l(w,v)D(4)l(4,6)134D(6)，因而源點(diǎn)到結(jié)點(diǎn)的最小距離minD(v),D(w)l(w,v)為4。其余步驟同理。所有步驟演算完畢即可得出結(jié)點(diǎn)1的最短路徑路由信息，如圖2所示。選擇結(jié)點(diǎn)1為源點(diǎn)步驟5步驟4圖2用Dijkstra算法得出結(jié)點(diǎn)1的最短路徑路由表通過(guò)上述Dijkstra算法的演算步驟可發(fā)現(xiàn)，如需在全局中搜索最短路徑的全局最優(yōu)解，每個(gè)步驟必須針對(duì)其余所有結(jié)點(diǎn)進(jìn)展一次距離的計(jì)算，以搜索出下一步可能存在的路徑。因此，Dijkstra算法的計(jì)算過(guò)程實(shí)際上

7、提供了一個(gè)全局搜索所有可能路徑的思路。換句話(huà)說(shuō)，Dijkstra算法想要尋找全局最短路徑，首先務(wù)必搜索出所有可能的路徑。2.3改進(jìn)的算法Dijkstra-like分析開(kāi)源的JAVA圖論庫(kù)JgraphtH過(guò)Dijkstra-like算法搜索全局所有可能路徑的計(jì)算方法實(shí)際上是基于經(jīng)典Dijkstra算法的完整計(jì)算流程來(lái)實(shí)現(xiàn)的。但是由于Dijkstr算法先天存在明顯的缺陷,Dijkstra-like算法對(duì)其進(jìn)展了如下改進(jìn)以滿(mǎn)足時(shí)間復(fù)雜性、空間復(fù)雜性等計(jì)算要求：1Dijkstra算法在通過(guò)距離計(jì)算尋找局部最優(yōu)路徑過(guò)程中，將所有可能路徑比照后，假設(shè)發(fā)現(xiàn)該路徑不是局部最優(yōu)解那么會(huì)將其丟棄。因此，Dijks

8、tra-like算法在搜索所有可能路徑那么需要將可能結(jié)果記錄下來(lái)并參與到下一步驟的計(jì)2Dijkstr算法處理過(guò)程中，在搜索所有可能路徑時(shí)需要遍歷所有結(jié)點(diǎn)進(jìn)展一次距離計(jì)算，哪怕是沒(méi)有直連關(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)從而過(guò)濾掉距離為的一類(lèi)結(jié)點(diǎn)，大大節(jié)約計(jì)算資源。三、源碼分析publicList<GraphPath<V,E>>getAllPaths(Set<V>sourceVertices,Set<

9、V>targetVertices,booleansimplePathsOnly,IntegermaxPathLength)/DecoratetheedgeswiththeminimumpathlengthsthroughthemMap<E,Integer>edgeMinDistancesFromTargets=edgeMinDistancesBackwards(targetVertices,maxPathLength);/GenerateallthepathsList<GraphPath<V,E>>allPaths=generatePaths(sour

10、ceVertices,targetVertices,simplePathsOnly,maxPathLength,edgeMinDistancesFromTargets);returnallPaths;edgeMinDistancesBackwards()數(shù)傳入終點(diǎn)和最大搜索路徑長(zhǎng)度，從終點(diǎn)開(kāi)場(chǎng)逐步往前搜索生成網(wǎng)絡(luò)拓樸圖中所有邊距離該終點(diǎn)的鏈路長(zhǎng)度，直至拓樸圖搜索完畢或者到達(dá)最大搜索長(zhǎng)度時(shí)完畢，準(zhǔn)備進(jìn)展下一步驟計(jì)算。generatePathsfi數(shù)傳入源點(diǎn)、終點(diǎn)和最大路徑長(zhǎng)度等信息，基于上一步驟的搜索結(jié)果從源點(diǎn)開(kāi)場(chǎng)逐步往后搜索到終點(diǎn)，直至找到該終點(diǎn)或者到達(dá)最大路徑長(zhǎng)度時(shí)完畢。搜索過(guò)程中保存每一條存在的路徑并將最終結(jié)果返回出來(lái)。四、接口調(diào)用List<GraphPath<V,E>>getAllPaths(Set<V>sourceVertices,Set<V&g