圖的最短路徑_dijkstra算法

《圖的最短路徑_dijkstra算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1基本圖算法陳嘉慶最短路徑問(wèn)題單源最短路徑Single-SourceShortestPath問(wèn)題:帶權(quán)有向圖G（E,V),找出從給定源頂點(diǎn)s到其它頂點(diǎn)v的權(quán)最小路徑?！白疃搪窂健?最小權(quán)路徑的權(quán)是路徑上所有邊的權(quán)之和。例：道路圖:從華師中山附中到市政府的最短路徑?若頂點(diǎn)序列{V0,V1,…,Vn}是從V0到Vn的最短路，則序列{V0,V1,…,Vn-1}必為從V0到Vn-1的最短路。貪心算法權(quán)非負(fù)的單源最短路徑算法（Dijkstra）12345612653723892v5v4v01005601010v1v2v3205030圖中從v0到其余各頂點(diǎn)之間的最短

2、路徑:v0到v1無(wú)v0到v2(v0,v2)10v0到v3(v0,v4,v3)50v0到v4(v0,v4)30v0到v5(v0,v4,v3,v5)60單源最短路徑基本思想：將圖中所有頂點(diǎn)分成兩組:S,V-S一組是包括已確定最短路徑的頂點(diǎn)的集合S，另一組是尚未確定的最短路徑的頂點(diǎn)集V-S。S初始僅包含源v0,不斷在V-S做貪心選擇擴(kuò)充集合S。權(quán)非負(fù)的單源最短路徑算法（Dijkstra）權(quán)非負(fù)的單源最短路徑算法（Dijkstra）初始時(shí),S僅包含源v0,特殊路徑：從源到G中某一頂點(diǎn)u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑。步驟:(1)取v0加入S中(2

3、)從V-S中取出具有當(dāng)前最短路徑長(zhǎng)度的頂點(diǎn)w加入S中。最短路徑——Dijkstra算法實(shí)例812345612653723892例求下圖中頂點(diǎn)1到其余各頂點(diǎn)的最短路徑。10123∞∞∞8510364142512(1)初始化:1到v,若有邊,則path[v]=邊;dist[i]=邊的值(2)選出dist[i]為最小值,則path[i]為1到i的最短路徑(3)修改經(jīng)過(guò)i更近的路徑(4)重復(fù)（2）（3）最短路徑——Dijkstra算法描述方法如下：（其中：path[v]和dist[v]表示從v0到v的最短路徑及其長(zhǎng)度）（1）對(duì)v0以外的各頂點(diǎn)vi，若<

4、v0,vi>存在，則將其作為v0到vi的（暫時(shí)的）最短路徑存放到path[v]中，將其權(quán)值作為對(duì)應(yīng)的路徑長(zhǎng)度存放到dist[v]中。（2）從未解頂點(diǎn)中選擇一個(gè)dist值最小的頂點(diǎn)v，則當(dāng)前的path[v]和dist[v]就是頂點(diǎn)v的最終解。（3）由于某些頂點(diǎn)經(jīng)過(guò)v可能會(huì)使得從v0到該頂點(diǎn)的路徑更近一些，因此，應(yīng)修改這些頂點(diǎn)的路徑及其長(zhǎng)度的值。（4）重復(fù)（2）（3），直到所有頂點(diǎn)求解完畢。9136425最短路徑——Dijkstra算法實(shí)例頂點(diǎn)pathdist12345610實(shí)例：123456126537238920123∞∞∞()(1,2)(1,3)()(

5、)()(1,3,2)85(1,3,4)(1,3,5)10(1,3,4,6)14(1,3,5,6)12Dijkstra算法：一般情況下，Dist[k]=<源點(diǎn)到頂點(diǎn)i的弧上的權(quán)值>或者=<源點(diǎn)到其它頂點(diǎn)的路徑長(zhǎng)度>+<其它頂點(diǎn)到頂點(diǎn)i的弧上的權(quán)值>設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Dist[i]表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)i的最短路徑的長(zhǎng)度。1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Dist[i]值。假設(shè)求得最短路徑的頂點(diǎn)為u，若Dist[u]+G.arcs[u][i]

6、為Dist[u]+G.arcs[u][i]V0和i之間存在弧V0和i之間不存在弧其中的最小值即為最短路徑的長(zhǎng)度。單源最短路徑Single-SourceShortestPathDijkstra的時(shí)間復(fù)雜度是O(N2)，它不能處理存在負(fù)邊權(quán)的情況。算法描述：設(shè)起點(diǎn)為s，dis[v]表示從s到v的最短路徑，pre[v]為v的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。a)初始化：dis[v]=∞(v≠s);dis[s]=0;pre[s]=0;b)For(i=1;i<=n;i++)1.在沒(méi)有被訪問(wèn)過(guò)的點(diǎn)中找一個(gè)頂點(diǎn)u使得dis[u]是最小的。2.u標(biāo)記為已確定最短路徑3.For與u

7、相連的每個(gè)未確定最短路徑的頂點(diǎn)vif(dis[u]+w[u][v]

8、點(diǎn)1到某一點(diǎn)V0的最短路徑要經(jīng)過(guò)中轉(zhuǎn)點(diǎn)Vi，那么中轉(zhuǎn)點(diǎn)Vi一定是先于V0被確定了