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

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

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

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

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

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

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

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

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