數據結構課件：第7章 圖4最短路徑

1、圖的連通性問題第7章 圖圖的定義和術語圖的存儲結構圖的遍歷有向無環(huán)圖及其應用最短路徑最短路徑問題7.6 最短路徑 典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？問題抽象：在帶權有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。（注：最短路徑與最小生成樹不同，路徑上不一定包含n個頂點）最短路徑問題7.6 最短路徑 一頂點到其余各頂點兩種常見的最短路徑問題：一、單源最短路徑用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑用Floyd（弗洛伊德）算法任意

2、兩頂點之間單源最短路徑 (Dijkstra算法)7.6 最短路徑 目的： 設一有向圖G=（V, E），已知各邊的權值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊上的權值大于或等于0。源點從FA的路徑有4條： FA： 24 FBA： 518=23 FBCA：5+7+9=21 FDCA：25+12+9=36又：從FB的最短路徑是哪條？從FC的最短路徑是哪條？v0(v0, v1)10源點終點 最 短路 徑路徑長度(v0, v1, v2)(v0, v3, v2)(v0, v3)30 v1 v2 v3 v4100(v0, v4)(v0, v3, v4)(v0, v3, v2, v4

3、)例： 60 509070討論：計算機如何自動求出這些最短路徑？(v0, v1, v2, v4)60 V0 V1 V2 V3 V4V0 10 30 100V1 50 V2 50 10 V3 20 60 V4 20 V0V2V1V4V3101003010506020單源最短路徑 (Dijkstra算法)7.6 最短路徑 V0 V1 V2 V3 V4V0 10 30 100V1 50 V2 50 10 V3 20 60 V4 20 V0V2V1V4V3101003010506020思考：單源最短路徑 (Dijkstra算法)7.6 最短路徑 算法思想： 先找出從源點v0到各終點vk的直達路徑(v0

4、, vk), 即通過一條弧到達的路徑。 從這些路徑中找出一條長度最短的路徑(v0, u), 然后對其余各條路徑進行適當調整： 若在圖中存在弧(u, vk)，且(v0, u)+(u, vk) (v0, vk), 則以路徑(v0, u, vk) 代替(v0, vk) 。在調整后的各條路徑中，再找長度最短的路徑，依此類推?？傊?，按路徑“長度” 遞增的次序來逐步產生最短路徑單源最短路徑 (Dijkstra算法)7.6 最短路徑 給定帶權有向圖G和源點v, 求從v到G中其余各頂點的最短路徑。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始點 終點 Di 最短路徑V1V2

5、V3V4 V510301001030100106030100106030100105030100(V0, V2)(V0, V4)(V0, V5)(V0, V2)(V0, V4)(V0, V5)(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5)(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5)(V0, V2)(V0, V4, V3)(V0, V4)(V0, V5)10503090(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V5)10503090(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V5)

6、10503060(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V3, V5)10503060(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V3, V5)(v0,v2)+ (v2,v3)(v0,v3)終點 從v0到各終點的dist值和最短路徑v1v2v3v4v5vjS之外的當前最短路徑之頂點60v0,v2,v350v0,v4,v330v0,v490v0,v4, v560v0,v4,v3,v5sv0,v2v0 ,v2 ,v4v0 ,v2 ,v4 ,v3v0 ,v2 ,v4 ,v3 ,v510v0,v230v0,v4100v0, v5v2v4v

7、3v5100v0, v5012345distw0 1 2 3 4 5與最小生成樹的不同點：路徑是累加的！10v0,v250v0,v4,v330v0,v4V5V0V2V4V1V31003010601020505所有頂點對之間的最短路徑(Floyd算法)7.6 最短路徑 問題描述： 已知一個各邊權值均大于 0 的帶權有向圖，對每對頂點 vivj，要求求出每一對頂點之間的最短路徑和最短路徑長度。 解決方案： 1. 每次以一個頂點為源點，重復執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對頂點之間的最短路徑?？偟膱?zhí)行時間為O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。時間復雜度也為O(n3)

8、。弗洛伊德算法可求解負權值網絡！弗洛伊德算法思想7.6 最短路徑 假設求從頂點Vi到Vj的最短路徑。如果從Vi到Vj有弧，則從Vi到Vj存在一條長度為arcsij的路徑，該路徑不一定是最短路徑，尚需進行n次試探。 首先考慮路徑（Vi,V0,Vj）是否存在（即判別（Vi,V0）、（V0,Vj）是否存在）。如存在，則比較（Vi,Vj）和（Vi,V0,Vj）的路徑長度，取長度較短者為從 Vi到Vj 的中間頂點的序號不大于0 的最短路徑。假如在路徑上再增加一個頂點 V1，依次類推?？赏瑫r求得各對頂點間的最短路徑。所有頂點對之間的最短路徑(Floyd算法)7.6 最短路徑 定義一個n階方陣序列 D(-1

9、),D(0),D(1),D(2),D(k),D(n-1)其中： D(-1)ij= arcsij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 0kn-1可見， D(1)ij就是從vi到vj的中間頂點的序號不大于1的最短路徑的長度; D(k)ij就是從vi到vj的中間頂點的序號不大于k的最短路徑的長度; D(n-1)ij就是從vi到vj的最短路徑的長度。所有頂點對之間的最短路徑(Floyd算法)7.6 最短路徑 0 4 116 0 23 0 各頂點間的最短路徑及其路徑長度 最短路徑弗洛伊德舉例 0 4 116 0 23 021CABCABCBCAABCABCAB

10、CABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB所有頂點對之間的最短路徑(Floyd算法)7.6 最短路徑5060123451038-4201734042-50560123451nil11nil12nilnilnil223nil3nilnilnil44nil4nilnil5nilnilnil5nilD0P0123451038-42017340425-

11、50-2560123451nil11nil12nilnilnil223nil3nilnilnil4414nil15nilnilnil5nilD1P1123451038-42017340425-50-2560123451nil11nil12nilnilnil223nil3nilnilnil4414nil15nilnilnil5nilD1P11234510384-42017340511425-50-2560123451nil11212nilnilnil223nil3nil224414nil15nilnilnil5nilD2P21234510384-42017340511425-50-2560123

12、451nil11212nilnilnil223nil3nil224414nil15nilnilnil5nilD2P21234510384-4201734051142-1-50-2560123451nil11212nilnilnil223nil3nil224434nil15nilnilnil5nilD3P31234510384-4201734051142-1-50-2560123451nil11212nilnilnil223nil3nil224434nil15nilnilnil5nilD3P312345103-14-4230-41-137405342-1-50-2585160123451nil142124nil421343nil214434nil154345nilD4P412345103-14-4230-41-137405342-1-50-2585160123451nil142124nil421343nil214434nil154345nilD4P412345101-32-4230-41-137405342-1-50-2585160123451nil345124nil421343nil214434nil154345nilD5P512345101-32-4230-41-137405342-1-50-258516