青圖-最短路徑2009級

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 單源點最短路徑：Dijstra算法 指的是對已知圖G=(V,E)，給定源頂點sV，找出s到圖中其它各頂點的最短路徑。 每對頂點間的最短路徑：Floyd算法 指的是對已知圖G=(V,E)，對任意的頂點Vi，VjV，找出從Vi到Vj的最短路徑。401820101510301235V1V4V3V2V6V540單源點最短路徑迪杰斯

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

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

4、圖的所有頂點都加到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 源點到vi中間只經(jīng)過S中頂點的最短路徑距離數(shù)組Distvi 源點到vi中間只經(jīng)過S中頂點的最短路徑長

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; 源點到vi中間只經(jīng)過S中頂點的最短路徑 “雙親”表示法，存儲頂點vi的“雙親”頂點( 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)/以u0為源點,求最短路徑 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; /求出的最短路徑終點加入頂點集S for(j=0; jG.vexnum; +j)/修改V-S中頂點到頂點集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 求每一對頂點之間的最短路徑弗洛伊德算法的基本思想 從vi到vj的所有可能存在的路徑中，選出一條長度最短的路徑。1) 不含其它頂點的路徑 vi,vj 2) 中間頂點序號不大于1的最短路徑 vi,vj3) 中間頂點序號不大于2的最短路徑 vi,vj n)

13、中間頂點序號不大于n的最短路徑 vi,vj7.6.2 求每一對頂點之間的最短路徑D(-1)ij=G.arcijD(k)ij= min D(k-1)ij, D(k-1)ik+D(k-1)ik 0kn-1 從vi到vj的中間頂點序號不大于1的最短路徑 (D(0)ij)為與 + 小者 從vi到vj的中間頂點序號不大于2的最短路徑 (D(1)ij)為中間頂點序號不大于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