數(shù)據(jù)結(jié)構(gòu)課件：第7章 圖4最短路徑

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

2、兩頂點(diǎn)之間單源最短路徑 (Dijkstra算法)7.6 最短路徑 目的： 設(shè)一有向圖G=（V, E），已知各邊的權(quán)值，以某指定點(diǎn)v0為源點(diǎn)，求從v0到圖的其余各點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。源點(diǎn)從FA的路徑有4條： FA： 24 FBA： 518=23 FBCA：5+7+9=21 FDCA：25+12+9=36又：從FB的最短路徑是哪條？從FC的最短路徑是哪條？v0(v0, v1)10源點(diǎn)終點(diǎn) 最 短路 徑路徑長度(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討論：計(jì)算機(jī)如何自動(dòng)求出這些最短路徑？(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 最短路徑 算法思想： 先找出從源點(diǎn)v0到各終點(diǎn)vk的直達(dá)路徑(v0

4、, vk), 即通過一條弧到達(dá)的路徑。 從這些路徑中找出一條長度最短的路徑(v0, u), 然后對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整： 若在圖中存在弧(u, vk)，且(v0, u)+(u, vk) (v0, vk), 則以路徑(v0, u, vk) 代替(v0, vk) 。在調(diào)整后的各條路徑中，再找長度最短的路徑，依此類推?？傊?，按路徑“長度” 遞增的次序來逐步產(chǎn)生最短路徑單源最短路徑 (Dijkstra算法)7.6 最短路徑 給定帶權(quán)有向圖G和源點(diǎn)v, 求從v到G中其余各頂點(diǎn)的最短路徑。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始點(diǎn) 終點(diǎn) 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)終點(diǎn) 從v0到各終點(diǎn)的dist值和最短路徑v1v2v3v4v5vjS之外的當(dāng)前最短路徑之頂點(diǎn)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與最小生成樹的不同點(diǎn)：路徑是累加的！10v0,v250v0,v4,v330v0,v4V5V0V2V4V1V31003010601020505所有頂點(diǎn)對(duì)之間的最短路徑(Floyd算法)7.6 最短路徑 問題描述： 已知一個(gè)各邊權(quán)值均大于 0 的帶權(quán)有向圖，對(duì)每對(duì)頂點(diǎn) vivj，要求求出每一對(duì)頂點(diǎn)之間的最短路徑和最短路徑長度。 解決方案： 1. 每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法n次。這樣，便可求得每一對(duì)頂點(diǎn)之間的最短路徑?？偟膱?zhí)行時(shí)間為O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。時(shí)間復(fù)雜度也為O(n3)

8、。弗洛伊德算法可求解負(fù)權(quán)值網(wǎng)絡(luò)！弗洛伊德算法思想7.6 最短路徑 假設(shè)求從頂點(diǎn)Vi到Vj的最短路徑。如果從Vi到Vj有弧，則從Vi到Vj存在一條長度為arcsij的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。 首先考慮路徑（Vi,V0,Vj）是否存在（即判別（Vi,V0）、（V0,Vj）是否存在）。如存在，則比較（Vi,Vj）和（Vi,V0,Vj）的路徑長度，取長度較短者為從 Vi到Vj 的中間頂點(diǎn)的序號(hào)不大于0 的最短路徑。假如在路徑上再增加一個(gè)頂點(diǎn) V1，依次類推?？赏瑫r(shí)求得各對(duì)頂點(diǎn)間的最短路徑。所有頂點(diǎn)對(duì)之間的最短路徑(Floyd算法)7.6 最短路徑 定義一個(gè)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的中間頂點(diǎn)的序號(hào)不大于1的最短路徑的長度; D(k)ij就是從vi到vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長度; D(n-1)ij就是從vi到vj的最短路徑的長度。所有頂點(diǎn)對(duì)之間的最短路徑(Floyd算法)7.6 最短路徑 0 4 116 0 23 0 各頂點(diǎn)間的最短路徑及其路徑長度 最短路徑弗洛伊德舉例 0 4 116 0 23 021CABCABCBCAABCABCAB

10、CABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB所有頂點(diǎn)對(duì)之間的最短路徑(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