帶權圖的最短路徑問題

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

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

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

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

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

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

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

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