算法最短路徑弗洛伊德Floyd算法演示文稿當前1頁，總共15頁。2求最短路徑步驟初始時設(shè)置一個n階方陣，令其對角線元素為0，若存在弧<Vi,Vj>，則對應元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值所有頂點試探完畢，算法結(jié)束3.Floyd算法思想：逐個頂點試探法當前2頁，總共15頁。

從圖的帶權(quán)鄰接矩陣G.arcs出發(fā)，假設(shè)求頂點Vi到Vj的最短路徑。如果從Vi到Vj有弧，則從Vi到Vj存在一條長度為G.arcs[i][j]的路徑，但該路徑是否一定是最短路徑，還需要進行n次試探。

1.第一次，判別（Vi,V0）和（V0，Vj），即判別(Vi,V0,Vj）是否存在，若存在，則比較（Vi,Vj）和(Vi,V0,Vj）的長度，取長度較短的為從Vi到Vj的中間頂點序號不大于0的最短路徑。當前3頁，總共15頁。

2.第二次，再加一個頂點V1，如果(Vi,…,V1）和(V1,…,Vj）分別是當前找到的中間頂點序號不大于0的最短路徑，那么(Vi,…,V1,…,Vj）就有可能是從Vi到Vj的中間頂點序號不大于1的最短路徑。將它和已經(jīng)得到的從Vi到Vj之間頂點序號不大于0的最短路徑相比較，取較短者為從Vi到Vj的中間頂點序號不大于1的最短路徑。

3.第三次，再加一個頂點V2，繼續(xù)進行試探。當前4頁，總共15頁。V2V3V0V1123456890123012301240092350801608888D(-1)=

D(-1)為有向網(wǎng)的鄰接矩陣第一步:以D(-1)為基礎(chǔ)，以V0為中間頂點，求從Vi到Vj的最短路徑。該路徑或者為從Vi到Vj的邊,或者為(Vi,V0)+(V0,Vj)。

D(0)[i][j]=min{D(-1)[i][j],D(-1)[i][0]+D(-1)[0][j]}47D(0)=

D(0)[i][j]為從Vi到Vj的中間頂點序號不大于0的最短路徑長度.V0當前5頁，總共15頁。V2V3V0V112345689

以D(0)為基礎(chǔ)，以V1為中間頂點，求從Vi,到Vj的最短路徑。該路徑或者為從Vi到Vj的邊,或者為從Vi開始通過V0或V1到達Vj的最短路徑。

D(1)[i][j]=min{D(0)[i][j],D(0)[i][1]+D(0)[1][j]}0123012301240092350801608888A(-1)=47D(0)=1036D(1)=V0V1V0V1當前6頁，總共15頁。V2V3V0V112345689

以D(1)為基礎(chǔ)，以V2為中間頂點，求從Vi,到Vj的最短路徑?；蛘邽閺腣i到Vj的邊,或者為從Vi開始通過V0,V1,V2到達Vj的最短路徑。

D(2)[i][j]=min{D(1)[i][j],D(1)[i][2]+D(1)[2][j]}0123012301240092350801608888A(-1)=47A(0)=1036D(1)=D(2)=12

910V0V1V2當前7頁，總共15頁。0123012301240092350801608888A(-1)=47A(0)=1036A(1)=D(2)=12

910D(3)=V2V3V0V112345689

以D(2)為基礎(chǔ)，以V3為中間頂點，求從Vi,到Vj的最短路徑?；蛘邽閺腣i到Vj的邊,或者為從Vi開始通過V0,V1,V2,V3到達Vj的最短路徑。

D(3)[i][j]=min{D(2)[i][j],D(2)[i][3]+D(2)[3][j]}

9

11

8V3V2V0V1

D(3)[i][j]即為從Vi到Vj的最短路徑長度.當前8頁，總共15頁。9ACB264311041160230初始：路徑：ABACBABCCA046602370加入B：路徑：ABABCBABCCACAB0411602370加入A：路徑：ABACBABCCACAB046502370加入C：路徑：ABABCBCABCCACAB例題：當前9頁，總共15頁。10例ACB264311初始：041160230length=011202300path=加入A：0411602370length=011202310path=加入B：046602370length=012202310path=加入C：046502370length=012302310path=當前10頁，總共15頁。114.論點：A(-1)[i][j]是從頂點vi到vj,中間頂點是

v1的最短路徑的長度,A(k)[i][j]是從頂點vi到vj,

中間頂點的序號不大于k的最短路徑的長度,A(n-1)[i][j]是從頂點vi到vj的最短路徑長度。證明：歸納證明，始歸納于s(上角標);(1)歸納基礎(chǔ)：當s=-1時，A(-1)[i][j]=Edge[i][j],vi到vj,不經(jīng)過任何頂點的邊，是最短路徑。(2)歸納假設(shè)：當s<k時，A(s)[i][j]是從頂點vi到vj,中間頂點的序號不大于s的最短路徑的長度;(3)當s=k時，當前11頁，總共15頁。12

ijkA(k-1)[i][k]A(k-1)[k][j]A(k-1)[i][j]因為：A(k)[i][j]=min{A(k-1)[i][j]，

A(k-1)[i][k]+A(k-1)[k][j]}由歸納假設(shè)知：A(k-1)[i][j]:是i到j(luò)的最短路徑(標號不高于k-1)；A(k-1)[i][k]:是i到k的最短路徑(標號不高于k-1)；A(k-1)[k][j]:是k到j(luò)的最短路徑(標號不高于k-1)；所以：A(k)[i][j]是i到j(luò)的最短路徑(標號不高于k)。當前12頁，總共15頁。13圖用鄰接矩陣存儲edge[][]存放最短路徑長度path[i][j]是從Vi到Vj的最短路徑上Vj前一頂點序號5.算法實現(xiàn)voidfloyd(){

for(inti=0;i<n;i++)//矩陣dist與path初始化for(int

j=0;j<n;j++){//置A(-1)dist[i][j]=Edge[i][j];

path[i][j]=-1;}//初始不經(jīng)過任何頂點for(intk=0;k<n;k++)//產(chǎn)生dist(k)及path(k)for(i=0;i<n;i++) for(j=0;j<n;j++)if(dist[i][k]+dist[k][j]<dist