1、1第14章 最短路徑問題 單源最短路徑所有頂點對間的最短路徑1第14章 最短路徑問題 單源最短路徑2單源最短路徑非加權圖的最短路徑 加權圖的最短路徑 帶有負權值的圖無環(huán)圖給出一個加權圖和圖上的一個節(jié)點s，找出s到圖中每一節(jié)點的最短路徑2單源最短路徑非加權圖的最短路徑 給出一個加權圖和圖上的一個3非加權的最短路徑采用廣度優(yōu)先搜索，它按層處理一層的所有結(jié)點：離起始結(jié)點最近的結(jié)點最先處理，距離最遠的最晚處理。具體過程：從s到s的最短路徑為0通過搜索S的所有鄰接結(jié)點就能找到離S距離為1的所有結(jié)點搜索離S距離為1的所有結(jié)點的鄰接結(jié)點就能找到距離為2的節(jié)點重復上述過程，直到所有節(jié)點都訪問到為止3非加權的最

2、短路徑采用廣度優(yōu)先搜索，它按層處理一層的所有結(jié)點4找v2到其他節(jié)點的最短距離V2V0V5V1V3V4V60V2V0V5V1V3V4V6011V2V0V5V1V3V4V601122V2V0V5V1V3V4V601122334找v2到其他節(jié)點的最短距離V2V0V5V1V3V4V60V5存儲設計數(shù)組distance：記錄從源點到達每個結(jié)點的最短距離。數(shù)組prev：記錄要到達此結(jié)點，必須到達的前一結(jié)點。例如，對于上圖中的結(jié)點v4，prevv4記錄的是v1。也就是說，從源點到達v4必須先到v1。而prevv1記錄的是v0，prevv0記錄的是v2。從prev數(shù)組，我們可以追溯到這條路徑。例如，對于v4，

3、我們可以追溯到這條路徑為v2-v0-v1-v4。 5存儲設計數(shù)組distance：記錄從源點到達每個結(jié)點的最短6過程抽象unweightedShortDistance(start) for （每個結(jié)點v） distancev = 無窮大； distancestart = 0; prevstart = 0; for (int curDistance = 0; curDistance 結(jié)點數(shù); +curDistance) for (每個結(jié)點u) if (distanceu = curDistance) for (u的每一個鄰接點v) if（distancev= 無窮大） distancev= cu

4、rDistanve+1； prevv = u； .6過程抽象unweightedShortDistance(s7分析算法的時間復雜度為O（|V|E|）。算法效率之所以低的原因之一在于：為保證所有結(jié)點都找到了最短路徑，算法假設最長的路徑是經(jīng)過所有的結(jié)點。該算法效率之所以低的第二個原因在于：內(nèi)層循環(huán)的設計。在處理距離為d的結(jié)點時，我們找到了所有距離為d+1的結(jié)點。但算法并沒有利用這個成果，而在下一個循環(huán)周期中又用順序查找的方法檢查了所有結(jié)點，從中挑出距離為d+1的結(jié)點。這浪費了大量的時間。7分析算法的時間復雜度為O（|V|E|）。8算法的改進外層循環(huán)沒必要執(zhí)行|V|次，只要所有的結(jié)點都已找到了最短

5、距離就可以了。第二層循環(huán)也沒必要執(zhí)行|V|次，只要檢查新找到最短路徑的結(jié)點。用一個隊列保存新找到路徑的結(jié)點8算法的改進外層循環(huán)沒必要執(zhí)行|V|次，只要所有的結(jié)點都已找9改進算法的偽代碼unweightedShortDistance(start) for （每個結(jié)點v） distance(v) = 無窮大； distancestart = 0; start入隊; while （隊列非空） 取出隊頭元素存入u； for (u的每一個鄰接點v) if（distancev= 無窮大） distancev= distanceu + 1； prevv = u； v入隊； . 9改進算法的偽代碼unweig

6、htedShortDistan10鄰接表中的實現(xiàn)template void adjListGraph :unweightedShortDistance (TypeOfVer start, TypeOfEdge noEdge) const linkQueue q; TypeOfEdge *distance = new TypeOfEdgeVers; int *prev = new int Vers; int u, sNo; edgeNode *p; for (int i = 0; i Vers; +i) distancei = noEdge; 10鄰接表中的實現(xiàn)template class Ty

7、peO11/尋找起始結(jié)點的編號 for (sNo = 0; sNo Vers; + sNo) if (verListsNo.ver = start) break; if (sNo = Vers) cout 起始結(jié)點不存在 next) if (distancep-end = noEdge) distancep-end = distanceu + 1; prevp-end = u; q.enQueue(p-end); /輸出最短路徑 for (i = 0; i Vers; +i) cout 從 start 到 verListi.ver 的路徑為: endl; printPath(sNo, i, p

8、rev); cout endl; 11/尋找起始結(jié)點的編號12隊列的變化： d2=00 5 d0=1, d5=11 3 d1=2, d3 = 234 d4=36 d6 = 36空 算法結(jié)束V2V0V5V1V3V4V612隊列的變化：V2V0V5V1V3V4V613printPath函數(shù)的實現(xiàn) 路徑的存儲不是正向的。即可以從第一個結(jié)點找到第二個結(jié)點，從第二個結(jié)點找到第三個結(jié)點，。而是逆向存儲的，即最后一個結(jié)點記住倒數(shù)第二個結(jié)點，倒數(shù)第二個結(jié)點記住倒數(shù)第三個結(jié)點，。適合用遞歸處理。于是我們定義了一個私有的遞歸成員函數(shù)printPath來輸出這條路徑。 13printPath函數(shù)的實現(xiàn) 路徑的存儲不

9、是正向的。即可14template void adjListGraph :printPath(int start, int end, int prev) const if (start = end) cout verListstart.ver ;return; printPath(start, prevend, prev); cout - verListend.ver ; 14template class TypeOfVer, c15函數(shù)的輸出從v2到v0的路徑為：v2 v0從v2到v1的路徑為：v2 v0 - v1從v2到v2的路徑為：v2從v2到v3的路徑為：v2 v0 v3從v2到v4的

10、路徑為：v2 v0 v3 v4從v2到v5的路徑為：v2 v5從v2到v6的路徑為：v2 v0 v3 v6 V2V0V5V1V3V4V615函數(shù)的輸出從v2到v0的路徑為：V2V0V5V1V3V416時間復雜度算法的主體是while循環(huán)，該循環(huán)一直執(zhí)行到隊列為空。而圖中的每個結(jié)點都必須而且僅入隊一次，因此該循環(huán)必須執(zhí)行|V|個循環(huán)周期。每個循環(huán)周期檢查出隊結(jié)點的所有邊，整個while循環(huán)檢查了圖中所有的邊。因此，while循環(huán)的運行時間為O（|E|）。前面的一些輔助工作，如初始化、尋找起始結(jié)點的編號等所需要的時間是O（|V|）。所以算法的總運行時間為O（|V|+|E|）。 16時間復雜度算法的

11、主體是while循環(huán)，該循環(huán)一直執(zhí)行到隊17單源最短路徑非加權圖的最短路徑 加權圖的最短路徑 帶有負權值的圖無環(huán)圖給出一個加權圖和圖上的一個節(jié)點s，找出s到圖中每一節(jié)點的最短路徑17單源最短路徑非加權圖的最短路徑 給出一個加權圖和圖上的一18Dijkstra算法保存了一個頂點集S。S中的頂點是已經(jīng)找到了最短路徑的頂點。開始時，頂點集合S只包含源點一個頂點。反復執(zhí)行以下循環(huán)，直至頂點集S 包含所有的頂點為止：對于在頂點集V - S中的每個頂點，考察新加入頂點集S中的結(jié)點是否有邊到達自己。如果存在，則檢查這條路徑是否比原來已知的路徑要短。如果是，則更新源點到此結(jié)點的距離和路徑；然后，從V S中尋找

12、一個路徑最短的結(jié)點，從源點到這個結(jié)點已經(jīng)不可能有更好的路徑了，把它加入頂點集S18Dijkstra算法保存了一個頂點集S。S中的頂點是已經(jīng)194V2V0V5V1V3V4V6421253102481654V2V0V5V1V3V4V642125310248165654V2V0V5V1V3V4V642125310248165654V2V0V5V1V3V4V6421253102481656579194V2V0V5V1V3V4V64212531024816204V2V0V5V1V3V4V64212531024816565794V2V0V5V1V3V4V64212531024816565794V2V0V5

13、V1V3V4V6421253102481656579204V2V0V5V1V3V4V6421253102481621存儲設計和非加權圖的實現(xiàn)中一樣，需要保存的距離和路徑信息還需要保存哪些結(jié)點在S中，哪些結(jié)點不在S中的信息。設計三個數(shù)組：distance、prev和known， 21存儲設計和非加權圖的實現(xiàn)中一樣，需要保存的距離和路徑信息22偽代碼void dijkstra( start ) for （圖中的每個頂點v） distancev = INFINITY; knownv = false; distancestart = 0; for (i = 1; i Vers; +i) v = 所有k

14、nown標記為false的結(jié)點中的路徑最短者； knownv = true; for （v的每一個鄰接點w） if (knownw 等于false & distancev + (v,w)的權值 distancew ) distancew = distancev + (v,w)的權值 Prevw = v; 22偽代碼void dijkstra( start )23鄰接表類中實現(xiàn)的Dijkstra算法 template void adjListGraph :dijkstra(TypeOfVer start, TypeOfEdge noEdge) const TypeOfEdge *distance

15、 = new TypeOfEdgeVers; int *prev = new int Vers; bool *known = new boolVers; int u, sNo, i, j; edgeNode *p; TypeOfEdge min; for (i = 0; i Vers; +i) /初始化 knowni = false; distancei = noEdge; 23鄰接表類中實現(xiàn)的Dijkstra算法 template 24for (sNo = 0; sNo Vers; +sNo) if (verListsNo.ver = start) break; if (sNo = Vers

16、) cout 起始結(jié)點不存在 endl; return; distancesNo = 0; prevsNo = sNo; for (i = 1; i Vers; +i) min = noEdge; for (j = 0; j Vers; +j) if (!knownj & distancej next) if (!knownp-end & distancep-end min + p-weight) distancep-end = min + p-weight; prevp-end = u; for (i = 0; i Vers; +i) /輸出所有的路徑信息 cout 從 start 到 ve

17、rListi.ver 的路徑為: endl; printPath(sNo, i, prev); cout t長度為： distancei endl; 24for (sNo = 0; sNo Vers; +25執(zhí)行dijkstra函數(shù)的過程 ：源點為v1udist 0prev0known0dist 1prev1known1dist 2prev2known2dist3prev3known3dist 4prev4known4dist 5prev5known5dist 6prev6known6, -, F0, 1, F, -, F, -, F, -, F, -, F, -, F1, -, F0, 1,

18、 T, -, F3, 1, F10, 1, F, -, F, -, F3, -, F0, 1, T5, 3, F3, 1, T5, 3, F11, 3, F7, 3, F29, 2, F0, 1, T5, 3, T3, 1, T5, 3, F10, 2, F7, 3, F49, 2, F0, 1, T5, 3, T3, 1, T5, 3, T10, 2, F7, 3, F69, 2, F0, 1, T5, 3, T3, 1, T5, 3, T8, 6, F7, 3, T59, 2, F0, 1, T5, 3, T3, 1, T5, 3, T8, 6, T7, 3, TV2V0V5V1V3V4V

19、6421253102481625執(zhí)行dijkstra函數(shù)的過程 ：源點為v1udist 26輸出結(jié)果從v1到v0的路徑為：v1 v3 v2 - v0 長度為：9從v1到v1的路徑為：v1 長度為：0從v1到v2的路徑為：v1 v3 v2 長度為：5從v1到v3的路徑為：v1 v3 長度為：3從v1到v4的路徑為：v1 v3 v4 長度為：5從v1到v5的路徑為：v1 v3 v6 - v5 長度為：8從v1到v6的路徑為：v1 v3 v6 長度為：726輸出結(jié)果從v1到v0的路徑為：27時間復雜度Dijkstra 算法運行時間主要由兩部分組成：查找路徑最短的尚未在S中的結(jié)點u，以及掃描u的鄰接點

20、，更新他們的距離。每次找出距離最短的結(jié)點所需的時間是O(|V|)，在整個算法的執(zhí)行過程中，尋找距離最短的結(jié)點將花去O(|V|2)的時間。更新V - S中的結(jié)點的距離所需的時間是O(|E|)總的時間復雜度是O(|E|+|V|2) = O(|V|2) 27時間復雜度Dijkstra 算法運行時間主要由兩部分組成28單源最短路徑非加權圖的最短路徑 加權圖的最短路徑 帶有負權值的圖無環(huán)圖給出一個加權圖和圖上的一個節(jié)點s，找出s到圖中每一節(jié)點的最短路徑28單源最短路徑非加權圖的最短路徑 給出一個加權圖和圖上的一29帶有負權值的圖如果一個圖帶有負權值的邊，Dijkstra算法無法正常工作V2V0V5V1V

21、3V4V64212331024-816如按Dijkstra算法，從結(jié)點2出發(fā)首先會認為結(jié)點5是已知節(jié)點，但事實上，2-0-3-5是一條更短的路徑。29帶有負權值的圖如果一個圖帶有負權值的邊，Dijkstra30一個直觀的解決方案對每條邊的權值都增加一個常量，使之消除負邊，然后再使用Dijkstra算法。問題：經(jīng)過邊數(shù)多的路徑，權值增加得也多，并不等價于原問題30一個直觀的解決方案對每條邊的權值都增加一個常量，使之消除31一個可行的解決方案將加權圖和非加權圖算法組合起來思想：放棄known的概念，窮舉所有的路徑，選擇最短的一條。實現(xiàn)：利用一個隊列開始時，將源點s放入隊列重復以下過程，直到隊列為空

22、：出隊一個節(jié)點v對v的所有鄰接點w，如果經(jīng)過v到w的距離比已知的s到w的距離短，則更新w的距離，并將w入隊31一個可行的解決方案將加權圖和非加權圖算法組合起來32算法分析適用于無負環(huán)的圖時間效益：每個節(jié)點至多出隊v次，運行時間是O(|E | |V|)32算法分析適用于無負環(huán)的圖33單源最短路徑非加權圖的最短路徑 加權圖的最短路徑 帶有負權值的圖無環(huán)圖給出一個加權圖和圖上的一個節(jié)點s，找出s到圖中每一節(jié)點的最短路徑33單源最短路徑非加權圖的最短路徑 給出一個加權圖和圖上的一34無環(huán)圖的最短路徑當圖中無環(huán)時，可以對Dijkstra算法進行改進，使之達到O(|V|+|E|)的時間效益思想：按照拓撲排

23、序的次序選擇結(jié)點34無環(huán)圖的最短路徑當圖中無環(huán)時，可以對Dijkstra算法35V2V0V5V1V3V4V642133102416拓撲排序：2，0，5，1，3，4，6dpdpdpdpdp200425321603504161645dp7335V2V0V5V1V3V4V642133102416拓撲排36第14章 最短路徑問題 單源最短路徑所有頂點對間的最短路徑36第14章 最短路徑問題 單源最短路徑37所有節(jié)點對的最短路徑問題方法一，對每一結(jié)點運行Dijkstra最短路徑算法；方法二，用Floyd算法。時間復雜性O(N3)。具體思想是一次將每個節(jié)點作為中間節(jié)點，看看從起始點到中間結(jié)點，再從中間節(jié)點

24、到終止點的距離是不是比已知的距離短。如是，則替代。37所有節(jié)點對的最短路徑問題方法一，對每一結(jié)點運行Dijks38Floyd 算法使用n行n列的矩陣A用于計算最短路徑。 初始時， A i, j = c i, j 進行n次迭代 在進行第 k 次迭代時，我們將使用如下的公式 Ak-1i,j Aki,j = MIN Ak-1i,k + Ak-1k,j 注意：第k次迭代時，針對結(jié)點k進行。原Ak-1 矩陣的第k行，第k列保持不變。左上至右下的對角線元素也不變。 38Floyd 算法使用n行n列的矩陣A用于計算最短路徑。39V1V2V053820 8 53 0 2 00 1 20120 8 53 0 2 00 8 53 0 8 2 00 7 53 0 8 5 2 00 8 53 0 8 5 2 0A0A2A1A初值39V1V2V053820 8 50 40存儲設計Floyd算法除了給出任意兩個結(jié)點之間的最短路徑之外，還需要給出路徑的組成。每條路徑信息也只保存這條路徑上的前一結(jié)點的信息。路徑信息的保存需要一個|V|V|的二維數(shù)組prev。previj的值表示從i到j的最短路徑上的前一結(jié)點的序號。40存儲設計Floyd算法除了給出任意