帶權(quán)圖的最短路徑問題

1、帶權(quán)圖的最短路徑問題/course_ware/data_structure/web/tu/tu7.5.1.htm1、帶權(quán)圖的最短路徑問題 帶權(quán)圖的最短路徑問題即求兩個頂點間長度最短的路徑。其中：路徑長度不是指路徑上邊數(shù)的總和，而是指路徑上各邊的權(quán)值總和。 路徑長度的的具體含義取決于邊上權(quán)值所代表的意義?！纠拷煌ňW(wǎng)絡(luò)中常常提出的如下問題就是帶權(quán)圖中求最短路徑的問題。 （1）兩地之間是否有路相通? （2）在有多條通路的情況下，哪一條最短?其中:交通網(wǎng)絡(luò)可以用帶權(quán)圖表示：圖中頂點表示城鎮(zhèn)，邊表示兩個城鎮(zhèn)之間的道路，邊上的權(quán)值可表示兩城鎮(zhèn)間的距離，交通費用或途中所需的時間等等。2、交通網(wǎng)絡(luò)的表示 由

2、于交通網(wǎng)絡(luò)存在有向性，所以一般以有向網(wǎng)絡(luò)表示交通網(wǎng)絡(luò)?！纠吭O(shè)A城到B城有一條公路，A城的海拔高于B城。若考慮到上坡和下坡的車速不同，則邊和邊上表示行駛時間的權(quán)值也不同。即和應(yīng)該是兩條不同的邊。3、源點和終點 習(xí)慣上稱路徑的開始頂點為源點(Source)，路徑的最后一個頂點為終點(Destination)。 為了討論方便，設(shè)頂點集V=0，1，n-1，并假定所有邊上的權(quán)值均是表示長度的非負(fù)實數(shù)。單源最短路徑問題(Single-Source Shortest-PathsProblem) 單源最短路徑問題：已知有向帶權(quán)圖(簡稱有向網(wǎng))G=(V，E)，找出從某個源點sV到V中其余各頂點的最短路徑。1、

3、邊上權(quán)值相等的有向網(wǎng)的單源最短路徑 用求指定源點的BFS生成樹的算法可解決2、迪杰斯特拉(Dijkstra)算法求單源最短路徑 由Dijkstra提出的一種按路徑長度遞增序產(chǎn)生各頂點最短路徑的算法。（1）按路徑長度遞增序產(chǎn)生各頂點最短路徑 若按長度遞增的次序生成從源點s到其它頂點的最短路徑，則當(dāng)前正在生成的最短路徑上除終點以外，其余頂點的最短路徑均已生成（將源點的最短路徑看作是已生成的源點到其自身的長度為0的路徑）?！纠吭谟邢蚓W(wǎng)G8中，假定以頂點0為源點，則它則其余各頂點的最短路徑按路徑遞增序排列如右表所示（2）算法基本思想 設(shè)S為最短距離已確定的頂點集（看作紅點集），V-S是最短距離尚未確

4、定的頂點集（看作藍(lán)點集）。初始化 初始化時，只有源點s的最短距離是已知的(SD(s)=0)，故紅點集S=s，藍(lán)點集為空。重復(fù)以下工作，按路徑長度遞增次序產(chǎn)生各頂點最短路徑 在當(dāng)前藍(lán)點集中選擇一個最短距離最小的藍(lán)點來擴(kuò)充紅點集，以保證算法按路徑長度遞增的次序產(chǎn)生各頂點的最短路徑。 當(dāng)藍(lán)點集中僅剩下最短距離為的藍(lán)點，或者所有藍(lán)點已擴(kuò)充到紅點集時，s到所有頂點的最短路徑就求出來了。 注意： 若從源點到藍(lán)點的路徑不存在，則可假設(shè)該藍(lán)點的最短路徑是一條長度為無窮大的虛擬路徑。 從源點s到終點v的最短路徑簡稱為v的最短路徑；s到v的最短路徑長度簡稱為v的最短距離，并記為SD(v)。（3）在藍(lán)點集中選擇一個

5、最短距離最小的藍(lán)點k來擴(kuò)充紅點集 根據(jù)按長度遞增序產(chǎn)生最短路徑的思想，當(dāng)前最短距離最小的藍(lán)點k的最短路徑是： 源點，紅點1，紅點2，紅點n，藍(lán)點k距離為：源點到紅點n最短距離+邊長 為求解方便，設(shè)置一個向量D0n-1，對于每個藍(lán)點v V-S，用Dv記錄從源點s到達(dá)v且除v外中間不經(jīng)過任何藍(lán)點(若有中間點，則必為紅點)的最短路徑長度（簡稱估計距離）。 若k是藍(lán)點集中估計距離最小的頂點，則k的估計距離就是最短距離，即若Dk=minDi iV-S，則Dk=SD(k)。 初始時，每個藍(lán)點v的Dc值應(yīng)為權(quán)w，且從s到v的路徑上沒有中間點，因為該路徑僅含一條邊。 注意： 在藍(lán)點集中選擇一個最短距離最小的藍(lán)

6、點k來擴(kuò)充紅點集是Dijkstra算法的關(guān)鍵 （4）k擴(kuò)充紅點集s后，藍(lán)點集估計距離的修改 將k擴(kuò)充到紅點后，剩余藍(lán)點集的估計距離可能由于增加了新紅點k而減小，此時必須調(diào)整相應(yīng)藍(lán)點的估計距離。 對于任意的藍(lán)點j，若k由藍(lán)變紅后使Dj變小，則必定是由于存在一條從s到j(luò)且包含新紅點k的更短路徑：P=。且Dj減小的新路徑P只可能是由于路徑和邊組成。 所以，當(dāng)length(P)=Dk+w小于Dj時，應(yīng)該用P的長度來修改Dj的值。（5）Dijkstra算法Dijkstra(G，D，s) /用Dijkstra算法求有向網(wǎng)G的源點s到各頂點的最短路徑長度 /以下是初始化操作 S=s；Ds=0； /設(shè)置初始的

7、紅點集及最短距離 for( all i V-S )do /對藍(lán)點集中每個頂點i Di=Gsi； /設(shè)置i初始的估計距離為w /以下是擴(kuò)充紅點集 for(i=0;iDk+Gkj) /新紅點k使原Dj值變小時，用新路徑的長度修改Dj， /使j離s更近。 Dj=Dk+Gkj； 【例】對有向網(wǎng)G8以0為源點執(zhí)行上述算法的過程及紅點集、k和D向量的變化見【 HYPERLINK 動畫.swf 參見動畫演示】。（6）保存最短路徑的Dijkstra算法 設(shè)置記錄頂點雙親的向量P0n-1保存最短路徑：當(dāng)頂點i無雙親時，令Pi=-1。 當(dāng)算法結(jié)束時，可從任一Pi反復(fù)上溯至根(源點)求得頂點i的最短路徑，只不過路徑

8、方向正好與從s到i的路徑相反。 具體的求精算法【參見教材】 。 Dijkstra算法的時間復(fù)雜度為O(n2)其他最短路徑問題 最短路徑問題的提法很多，其它的最短路徑問題均可用單源最短路徑算法予以解決：單目標(biāo)最短路徑問題(Single-Destination Shortest-Paths Problem)：找出圖中每一頂點v到某指定頂點u的最短路徑。只需將圖中每條邊反向，就可將這一問題變?yōu)閱卧醋疃搪窂絾栴}，單目標(biāo)u變?yōu)閱卧袋cu。單頂點對間最短路徑問題(Single-Pair Shortest-Path Problem)：對于某對頂點u和v，找出從u到v的一條最短路徑。顯然，若解決了以u為源點的單源最短路徑問題，則上述問題亦迎刃而