青圖-最短路徑2009級(jí)

1、7.6 最 短 路 徑最短路徑最短路徑：長度最小的路徑路徑長度：路徑上邊的權(quán)值之和 V1到V5:路徑: V1,V5 40 V1,V2,V5 58 V1,V3,V4,V5 60 V1,V3,V4,V2,V5 53401820101510301235V1V4V3V2V6V540 單源點(diǎn)最短路徑：Dijstra算法 指的是對(duì)已知圖G=(V,E)，給定源頂點(diǎn)sV，找出s到圖中其它各頂點(diǎn)的最短路徑。 每對(duì)頂點(diǎn)間的最短路徑：Floyd算法 指的是對(duì)已知圖G=(V,E)，對(duì)任意的頂點(diǎn)Vi，VjV，找出從Vi到Vj的最短路徑。401820101510301235V1V4V3V2V6V540單源點(diǎn)最短路徑迪杰斯

2、特拉算法(Dijkstra) 輸入數(shù)據(jù):帶權(quán)圖 輸出數(shù)據(jù):源點(diǎn)s到圖中其它各頂點(diǎn)的最短路徑 V1 V3 10 V1 V3 V4 25 V1 V3 V4 V2 35 V1 V5 40 V1 V5 V6 52 401820101510301235V1V4V3V2V6V540迪杰斯特拉算法基本思想按長度遞增的順序求解最短路徑迪杰斯特拉算法(Dijkstra)把圖中所有頂點(diǎn)分成兩組第1組S包括已求得最短路徑的頂點(diǎn),初始時(shí),只S=源頂點(diǎn);第2組V-S包括尚未求得最短路徑的頂點(diǎn)；每次從第2組中選擇與源點(diǎn)距離最小(路徑長度最短)的頂點(diǎn)，加入第1組， 直至把圖的所有頂點(diǎn)都加到進(jìn)第1組;401820101510

3、301235V1V4V3V2V6V540 設(shè)v1是源點(diǎn)，(第1組) S=已求得最短路徑的頂點(diǎn)集合。 初始時(shí) S=v1; 1）長度最短的最短路徑是所有(v第2組)中長度最小者。不妨設(shè)該頂點(diǎn)為u， 長度最短，將u加入S；S=V1S=V1,V3124040181015103035V1V4V2V6V5V320124040181015103035V1V4V2V6V5V320迪杰斯特拉算法基本步驟： (Dijkstra) 2）下一條長度最短的最短路徑是所有路徑(v1,vi1, vi2, vik, v) (vijS(第1組), v第2組)中長度最小者,設(shè)該路徑的終點(diǎn)為w，將w加入S中； 3）重復(fù) 2）直至把

4、圖的所有頂點(diǎn)都加到S中。124040181015103035V1V4V2V6V5V32020124040181015103035V1V4V2V6V5V3迪杰斯特拉算法基本步驟S=V1,V3,V4S=V1,V315404018201010351230V1V4V2V6V5V3S=V112404018101530201035V1V4V2V6V5V3S=V1,V312404018101510303520V1V4V2V6V5V3S=V1,V312404018101510303520V1V4V2V6V5V3S=V1,V3,V412404018101510303520V1V4V2V6V5V3S=V1,V3,

5、V412404018101510303520V1V4V2V6V5V3S=V1,V3,V4,V212404018101510303520V1V4V2V6V5V3S=V1,V3,V4,V212404018101510303520V1V4V2V6V5V3S=V1,V3,V4,V2,V5124040181015103035V1V4V2V6V5V320S=V1,V3,V4,V2,V5124040181015103035V1V4V2V6V5V320S=V1,V3,V4,V2,V5,V6路徑數(shù)組Pathvi 源點(diǎn)到vi中間只經(jīng)過S中頂點(diǎn)的最短路徑距離數(shù)組Distvi 源點(diǎn)到vi中間只經(jīng)過S中頂點(diǎn)的最短路徑長

6、度12404018101510303520V1V4V2V6V5V3 0 35 10 25 40 55 Dist (v1,v3,v4,v2) (v1,v3) (v1,v3,v4) (v1,v5) (v1,v3,v4,v6) Path 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6) 0 40 10 I NFINITY 40 INFINITY Dist (v1,v2) (v1,v3) (v1,v5) Path 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6)15404018201010351230V1V4V2V6V5V312404018101510303

7、52012404018101530352010V1V4V2V6V5V3V1V4V2V6V5V3 0 40 10 25 40 INFINITY Dist (v1,v2) (v1,v3) (v1,v3,v4) (v1,v5) Path 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6)20124040181015103035V1V2V6V5V3V420124040181015103035V1V2V6V5V3V4 0 35 10 25 40 55 Dist (v1,v3,v4,v2) (v1,v3) (v1,v3,v4) (v1,v5) (v1,v3,v4,v6) Path 0(

8、v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6)124040181015103035V1V2V6V5V3V42020124040181015103035V1V2V6V5V3V4 0 35 10 25 40 55 Dist (v1,v3,v4,v2) (v1,v3) (v1,v3,v4) (v1,v5) (v1,v3,v4,v6) Path 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6)124040181015103035V1V2V6V5V3V42020124040181015103035V1V2V6V5V3V4 0 35 10 25 40 52 Dis

9、t (v1,v3,v4,v2) (v1,v3) (v1,v3,v4) (v1,v5) (v1,v5,v6) Path 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6) 0 35 10 25 40 52 Dist (v1,v3,v4,v2) (v1,v3) (v1,v3,v4) (v1,v5) (v1,v5,v6) Path 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6)20124040181015103035V1V3V4V2V5V6 -1 3(v4) 0(v1) 2(v3) 0(v1) 4(v5) Path 0(v1) 1(v2) 2(v3) 3(

10、v4) 4(v5) 5(v6)路徑數(shù)組 int Pathvi; 源點(diǎn)到vi中間只經(jīng)過S中頂點(diǎn)的最短路徑 “雙親”表示法，存儲(chǔ)頂點(diǎn)vi的“雙親”頂點(diǎn)( S)20124040181015103035V1V3V4V2V5V6 0 35 10 25 40 52 Dist 1 1 1 1 1 1 finalvoid SPath_Dij(MGraph G, int u0, int Dist,int Path,int final)/以u(píng)0為源點(diǎn),求最短路徑 for(i=0; iG.vexnum; +i) finali=0; Disti=G.arcsu0i; if(DistiINFINITY) Pathi=u

11、0; else Pathi=-1; / for finalu0=1; for (i=1; iG.vexnum; +i)/求G.vexnum-1條最短路徑 k=SelectMin(Dist, final); /在 Dist中選擇最小者 finalk=1; /求出的最短路徑終點(diǎn)加入頂點(diǎn)集S for(j=0; jG.vexnum; +j)/修改V-S中頂點(diǎn)到頂點(diǎn)集S的距離 if (!finalj&(Distk+G.arcskj)Distj) Distj= Distk+G.arcskj; Pathj=k; /for /SPath_Dijvoid PrintPath(MGraph G, int i, i

12、nt Path) if(Path i!=-1) PrintPath(G, Pathi, Path); printf(“, ”); PrintVextex(G ,i); -1 3 0 2 0 4 Path20124040181015103035V1V3V4V2V5V6 0(v1) 1(v2) 2(v3) 3(v4) 4(v5) 5(v6)7.6.2 求每一對(duì)頂點(diǎn)之間的最短路徑弗洛伊德算法的基本思想 從vi到vj的所有可能存在的路徑中，選出一條長度最短的路徑。1) 不含其它頂點(diǎn)的路徑 vi,vj 2) 中間頂點(diǎn)序號(hào)不大于1的最短路徑 vi,vj3) 中間頂點(diǎn)序號(hào)不大于2的最短路徑 vi,vj n)

13、中間頂點(diǎn)序號(hào)不大于n的最短路徑 vi,vj7.6.2 求每一對(duì)頂點(diǎn)之間的最短路徑D(-1)ij=G.arcijD(k)ij= min D(k-1)ij, D(k-1)ik+D(k-1)ik 0kn-1 從vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑 (D(0)ij)為與 + 小者 從vi到vj的中間頂點(diǎn)序號(hào)不大于2的最短路徑 (D(1)ij)為中間頂點(diǎn)序號(hào)不大于1的最短路徑 vi,vj 與vi,v2 + v2,vj小者CBAD151245ABCD A B C D151452D(-1)ij=ABADCACDBCDBABADCACDBCDBABCDA B C D1514526D(0)ijABADCA

14、CDBCDBABCABADCACDBCDBCBAD151245ABCDA B C D151452526CBAD151245D(1)ijABCABADCACDBCDBABCABADCACDBCDBABABCCABADCACDBCDBDBCABCDA B C D1414521065263CBAD151245D(2)ijABABCCABADCACDBCDBDBCABABCDBCCABADCACDBCDBDBCABABCDBCACABABCDCACDBCDBCBCADBDBCCBAD151245D(3)ijABABCDBCACABABCDCACDBCDBCBCADBDBCABABCDBCACABABCDCACDBCD