算法12最短路徑弗洛伊德Floyd算法

11.問題的提出：已知一個各邊權值均大于0的帶權有向圖，對每一對頂點vi

vj，要求求出vi

與vj之間的最短路徑和最短路徑長度。2.解決辦法方法一：每次以一個頂點為源點，重復執(zhí)行Dijkstra算法n次——T(n)=O(n3)方法二：弗洛伊德(Floyd)算法2求最短路徑步驟初始時設置一個n階方陣，令其對角線元素為0，若存在弧<Vi,Vj>，則對應元素為權值；否則為逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值所有頂點試探完畢，算法結束3.Floyd算法思想：逐個頂點試探法從圖的帶權鄰接矩陣G.arcs出發(fā)，假設求頂點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的最短路徑。

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

3.第三次，再加一個頂點V2，繼續(xù)進行試探。

V2V3V0V1123456890123012301240092350801608888D(-1)=

D(-1)為有向網(wǎng)的鄰接矩陣

第一步:以D(-1)為基礎，以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的最短路徑長度.V0V2V3V0V112345689

以D(0)為基礎，以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)=V0V1V0V1V2V3V0V112345689

以D(1)為基礎，以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

910V0V1V20123012301240092350801608888A(-1)=47A(0)=1036A(1)=D(2)=12

910D(3)=V2V3V0V112345689

以D(2)為基礎，以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的最短路徑長度.9ACB264311041160230初始：路徑：ABACBA

BCCA046602370加入B：路徑：ABABCBA

BCCA

CAB0411602370加入A：路徑：ABACBA

BCCACAB046502370加入C：路徑：AB

ABCBCA

BCCA

CAB例題：10例ACB264311初始：041160230length=011202300path=加入A：0411602370length=011202310path=加入B：046602370length=012202310path=加入C：046502370length=012302310path=114.論點：A(-1)[i][j]是從頂點vi到vj,中間頂點是

v1的最短路徑的長度,A(k)[i][j]是從頂點vi到vj,中間頂點的序號不大于k的最短路徑的長度,A(n-1)[i][j]是從頂點vi到vj的最短路徑長度。證明：歸納證明，始歸納于s(上角標);(1)歸納基礎：當s=-1時，A(-1)[i][j]=Edge[i][j],vi到vj,不經(jīng)過任何頂點的邊，是最短路徑。(2)歸納假設：當s<k時，A(s)[i][j]是從頂點vi到vj,中間頂點的序號不大于s的最短路徑的長度;(3)當s=k時，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]}由歸納假設知：A(k-1)[i][j]:是i到j的最短路徑(標號不高于k-1)；A(k-1)[i][k]:是i到k的最短路徑(標號不高于k-1)；A(k-1)[k][j]:是k到j的最短路徑(標號不高于k-1)；所以：A(k)[i][j]是i到j的最短路徑(標號不高于k)。

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[i][j]){

dist[i][j]=dist[i][k]+dist[k][j];

path[i][j]=k;}//縮短路徑,繞過k到j

}//floyd

146.算法分析：設最內層循環(huán)體為基本操作，算法有三層循環(huán)