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

11.問題的提出：已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對(duì)每一對(duì)頂點(diǎn)vi

vj，要求求出vi

與vj之間的最短路徑和最短路徑長(zhǎng)度。2.解決辦法方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次——T(n)=O(n3)方法二：弗洛伊德(Floyd)算法2求最短路徑步驟初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線元素為0，若存在弧<Vi,Vj>，則對(duì)應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值所有頂點(diǎn)試探完畢，算法結(jié)束3.Floyd算法思想：逐個(gè)頂點(diǎn)試探法從圖的帶權(quán)鄰接矩陣G.arcs出發(fā)，假設(shè)求頂點(diǎn)Vi到Vj的最短路徑。如果從Vi到Vj有弧，則從Vi到Vj存在一條長(zhǎng)度為G.arcs[i][j]的路徑，但該路徑是否一定是最短路徑，還需要進(jìn)行n次試探。

1.第一次，判別（Vi,V0）和（V0，Vj），即判別(Vi,V0,Vj）是否存在，若存在，則比較（Vi,Vj）和(Vi,V0,Vj）的長(zhǎng)度，取長(zhǎng)度較短的為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑。

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

3.第三次，再加一個(gè)頂點(diǎn)V2，繼續(xù)進(jìn)行試探。

V2V3V0V1123456890123012301240092350801608888D(-1)=

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

第一步:以D(-1)為基礎(chǔ)，以V0為中間頂點(diǎn)，求從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的中間頂點(diǎn)序號(hào)不大于0的最短路徑長(zhǎng)度.V0V2V3V0V112345689

以D(0)為基礎(chǔ)，以V1為中間頂點(diǎn)，求從Vi,到Vj的最短路徑。該路徑或者為從Vi到Vj的邊,或者為從Vi開始通過V0或V1到達(dá)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)為基礎(chǔ)，以V2為中間頂點(diǎn)，求從Vi,到Vj的最短路徑?；蛘邽閺腣i到Vj的邊,或者為從Vi開始通過V0,V1,V2到達(dá)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)為基礎(chǔ)，以V3為中間頂點(diǎn)，求從Vi,到Vj的最短路徑。或者為從Vi到Vj的邊,或者為從Vi開始通過V0,V1,V2,V3到達(dá)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的最短路徑長(zhǎng)度.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.論點(diǎn)：A(-1)[i][j]是從頂點(diǎn)vi到vj,中間頂點(diǎn)是

v1的最短路徑的長(zhǎng)度,A(k)[i][j]是從頂點(diǎn)vi到vj,中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度,A(n-1)[i][j]是從頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。證明：歸納證明，始?xì)w納于s(上角標(biāo));(1)歸納基礎(chǔ)：當(dāng)s=-1時(shí)，A(-1)[i][j]=Edge[i][j],vi到vj,不經(jīng)過任何頂點(diǎn)的邊，是最短路徑。(2)歸納假設(shè)：當(dāng)s<k時(shí)，A(s)[i][j]是從頂點(diǎn)vi到vj,中間頂點(diǎn)的序號(hào)不大于s的最短路徑的長(zhǎng)度;(3)當(dāng)s=k時(shí)，12

ijkA(k-1)[i][k]A(k-1)[k][j]A(k-1)[i][j]因?yàn)椋篈(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ò)的最短路徑(標(biāo)號(hào)不高于k-1)；A(k-1)[i][k]:是i到k的最短路徑(標(biāo)號(hào)不高于k-1)；A(k-1)[k][j]:是k到j(luò)的最短路徑(標(biāo)號(hào)不高于k-1)；所以：A(k)[i][j]是i到j(luò)的最短路徑(標(biāo)號(hào)不高于k)。

13圖用鄰接矩陣存儲(chǔ)edge[][]存放最短路徑長(zhǎng)度path[i][j]是從Vi到Vj的最短路徑上Vj前一頂點(diǎn)序號(hào)5.算法實(shí)現(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)過任何頂點(diǎn)

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(luò)

}//floyd

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