基于Floyd算法的最短路徑優(yōu)化研究

邱曉鵬，王麗君

(1.隴南師范高等專科學(xué)校 數(shù)信學(xué)院，甘肅 成縣 742500；2.隴南師范高等專科學(xué)校 電子商務(wù)學(xué)院，甘肅 成縣 742500)

0 引言

研究最短路徑的算法比較多，像Dijkstra、Bellman-Ford和Floyd算法等，其算法優(yōu)化問題是一個(gè)研究熱點(diǎn).在多源最短路徑算法基礎(chǔ)上，相對(duì)于Dijkstra和Bellman-Ford算法，F(xiàn)loyd算法是一種更快的算法，也是比較簡(jiǎn)單的算法.但在某些情況下,Floyd算法解決實(shí)際問題時(shí)，會(huì)發(fā)現(xiàn)算法的執(zhí)行時(shí)間只能勉強(qiáng)達(dá)到時(shí)間限制要求.優(yōu)化改進(jìn)后的算法在時(shí)間復(fù)雜度和空間復(fù)雜度上都有所降低.

1 Floyd算法分析

1.1 路徑中的途經(jīng)點(diǎn)

假設(shè)有連接兩個(gè)頂點(diǎn)u和v的路徑.此路徑肯定會(huì)經(jīng)過起點(diǎn)u和終點(diǎn)v，此外還會(huì)經(jīng)過其他頂點(diǎn).比如，沒有直接連接u和v的路徑，或者經(jīng)過其他頂點(diǎn)的路徑比直接連接的路徑更短，此時(shí)就會(huì)經(jīng)過其他頂點(diǎn).路徑經(jīng)過的頂點(diǎn)就成為途經(jīng)點(diǎn).

只將頂點(diǎn)集合S中的頂點(diǎn)用作途經(jīng)點(diǎn)得到的從u到v的最短距離，記作DS(u,v).例如，圖1的拓?fù)鋱D中，D{}(a,b)=5，而D{c,d}(a,b)=4.如果不需要使用S中的所有頂點(diǎn)，則有D{a,c,d,e,g,f}(b,f)=D{}(b,f)=3.使用這種標(biāo)記法時(shí)，最終想得到的結(jié)果值是將整個(gè)頂點(diǎn)的集合V都用作途經(jīng)點(diǎn)的DV(u,v).連接兩個(gè)頂點(diǎn)的邊線中,最短邊線的長(zhǎng)度w(u,v)等于D{}(u,v).

假設(shè)有以S中的頂點(diǎn)為途經(jīng)點(diǎn)而得到的從u到v的最短路徑.選擇S中的頂點(diǎn)之一并標(biāo)為x.此時(shí)，有兩種形態(tài)，路徑不經(jīng)過x：此路徑只將S-{x}中的頂點(diǎn)用作途經(jīng)點(diǎn)；路徑經(jīng)過x：此時(shí)，路徑可分為u到x的區(qū)間和x到v的區(qū)間.這兩個(gè)子路徑必須是連接u和x、x和v的最短路徑.很顯然，兩個(gè)子路徑并不會(huì)途經(jīng)x，所以只會(huì)將S-{x}中的頂點(diǎn)用作途徑點(diǎn).

將S用作途經(jīng)點(diǎn)的從u到v的最短路徑會(huì)選擇上述路徑中較短的一個(gè)，因此，可以把Ds(u,v)按照歸方式定義為如下形式.

Floyd算法會(huì)計(jì)算出圖1部分拓?fù)鋱D的所有成對(duì)頂點(diǎn)之間的最短距離，并保存到二維數(shù)組tpt[][]中，此數(shù)組的元素tpt[u][v]表示從頂點(diǎn)u到v的最短距離.其運(yùn)算方式不同于迪杰斯特拉算法(Dijkstra)[1]和貝爾曼-福特算法(Bellman-Ford)[2].迪杰斯特拉算法和貝爾曼-福特算法都是從一個(gè)起點(diǎn)出發(fā)，計(jì)算到各頂點(diǎn)的距離.不過，根據(jù)問題的需求，有時(shí)候需要對(duì)所有成對(duì)頂點(diǎn)求出最短距離.要解決此問題，可以用迪杰斯特拉算法，只要把各頂點(diǎn)都視為起點(diǎn)，并反復(fù)執(zhí)行迪杰斯特拉算法即可實(shí)現(xiàn).若存在負(fù)權(quán)值，就改用貝爾曼-福特算法.這樣就會(huì)大大增加時(shí)間和空間復(fù)雜度.其實(shí)，想要對(duì)所有成對(duì)頂點(diǎn)求出最短距離，F(xiàn)loyd多源最短路徑算法是一種更快的算法[3]，更是最簡(jiǎn)單的算法.而且已有現(xiàn)成的Floyd算法的原型.

圖1 拓?fù)鋱D

1.2 Floyd算法的原型

簡(jiǎn)單修改上述遞歸式，就能利用動(dòng)態(tài)規(guī)劃法[4]解決多源最短路徑問題.設(shè)Sk={0,1,2,…,k}，Ck=DSk.那么，Ck(u,v)就等于只把0到k的頂點(diǎn)用作途經(jīng)點(diǎn)時(shí)，得到從u到v的最短距離.利用此標(biāo)記法就能把上述遞歸式改寫為如下形式.

遞歸式中，Ck的所有值只依賴于Ck-1，所以利用選代動(dòng)態(tài)規(guī)劃法就非常容易求解.代碼1-1是實(shí)現(xiàn)這種方法的代碼.此代碼中，Ck(u,v)的值會(huì)保存到C[k][u][v].因此，函數(shù)終止運(yùn)行后，若想知道u到v的最短距離，只需查看C[V-1][u][v]即可.

代碼1-1Floyd算法的原型

int v;

int tpt[MAX_V] [MAX_V];

int C [MAX_V] [MAX_V] [MAX_V];

vold allPairShortestPath1(){

for(int i=0;i

for(int j=0;j

if(i!=j)

C[0][i][j]=min (tpt[i][j], tpt[i][0], tpt[0][j]);

else

C[0][i][j]=0

for(int k= 1：k

for(int i=0：i

for(int j=0;j

C[k][i][j]=min (tpt[k-1][i][j], tpt[k-1] [i][k], tpt[k-1] [k][j]);

}

要注意，計(jì)算C(0)時(shí)，C[0][u][v]總是會(huì)初始化為0，因?yàn)榧词箾]有額外到達(dá)自己本身的邊線，其最短距離也會(huì)是0.顯而易見此算法的時(shí)間復(fù)雜度也由三重for循環(huán)語(yǔ)句決定，每個(gè)for語(yǔ)句會(huì)執(zhí)行O(|V|)次，所以整個(gè)算法的時(shí)間復(fù)雜度是O(|V|3).

2 Floyd算法內(nèi)存使用量的優(yōu)化

Floyd最短路徑算法在此基礎(chǔ)上更進(jìn)一步，在不使用額外數(shù)組的前提下，在保存圖結(jié)構(gòu)加權(quán)值的鄰接矩陣中計(jì)算遞歸式的結(jié)果值.利用滑動(dòng)窗口就能把此代碼的內(nèi)存使用量減少至O(|V|2).只要有Ck-1就能求出Ck的值，所以沒有必要繼續(xù)保存Ck-2、Ck-3等的結(jié)果值.利用這一特點(diǎn)就能把代碼1-1中的數(shù)組大小減少至2×|V|×|V|.因?yàn)?，只需要把Ck(u,v)的值保存到C[k%2][u][v]即可.

代碼1-1使用過的遞歸式中，為了計(jì)算出Ck(u,v)，需要的只是Ck-1(u,k)和Ck-1(k,v).而Ck-1(u,k)和Ck(u,k)區(qū)別如下：1、Ck-1(u,k)=把起點(diǎn)到第k-1個(gè)頂點(diǎn)用作途經(jīng)點(diǎn)的從u到k的最小長(zhǎng)度；2、Ck(u,k)=把起點(diǎn)到第k個(gè)頂點(diǎn)用作途經(jīng)點(diǎn)的從u到k的最小長(zhǎng)度.

可以確定起點(diǎn)或終點(diǎn)是第k個(gè)頂點(diǎn)時(shí)，把k添加到可使用途經(jīng)點(diǎn)的目錄將沒有任何意義.這就等于，“經(jīng)過地鐵站到達(dá)63大廈的路徑”和“經(jīng)過地鐵站和63大廈到達(dá)63大廈的路徑”并沒有什么區(qū)別.由此可知，不用區(qū)分Ck-1和Ck的值，可以直接混用.因此，不用區(qū)分C[k%2]和C[(k-1)%2]，而可以直接在同一二維數(shù)組中混用.

代碼4-1的Floyd算法根本不生成額外的數(shù)組C，而直接在鄰接矩陣tpt中計(jì)算最短距離.此算法的時(shí)間復(fù)雜度還是O(|V|3)、而空間復(fù)雜度減少到了O(|V|2).通過圖結(jié)構(gòu)的鄰接矩陣表示法，tpt[u][v]等于從u到v的邊線加權(quán)值.若沒有邊線，就代入極大值.

代碼4-1-Floyd算法的實(shí)現(xiàn)方法

int v;

int tpt[MAX_V] [MAX_V];

vold floyd(){

for(int i=0;i

for(int k=0;k

for(int i=0;i

for(int j=0;j

tpt[i][j]= min (tpt[i][j], tpt[i][k]+ tpt[k][j]);

}

3 Floyd算法執(zhí)行優(yōu)化

某些情況下利用Floyd算法解決實(shí)際問題時(shí)，會(huì)發(fā)現(xiàn)該算法的執(zhí)行時(shí)間只能勉強(qiáng)達(dá)到時(shí)間限制要求.對(duì)于這種情況，可以在不改變時(shí)間復(fù)雜度的前提下，依然能對(duì)算法進(jìn)行優(yōu)化，那就是在第二個(gè)for語(yǔ)句之后，確認(rèn)從i到k的路徑是否實(shí)際存在.如果從i到k的路徑不存在，就沒有必要對(duì)j執(zhí)行for語(yǔ)句.這樣會(huì)大大降低了運(yùn)算時(shí)間，巧妙地優(yōu)化了Floyd算法.

4 Floyd優(yōu)化改進(jìn)算法的實(shí)現(xiàn)

Floyd算法的執(zhí)行方式不同于向最短路徑逐條添加邊線的迪杰斯特拉算法和貝爾曼-福特算法，所以計(jì)算實(shí)際路徑的過程也大不相同.執(zhí)行Floyd算法后，為了計(jì)算兩個(gè)頂點(diǎn)之間的最短路徑，需要把各成對(duì)頂點(diǎn)u、v最后一次更新tpt[u][v]時(shí)使用過的k值保存起來.假設(shè)此頂點(diǎn)的序號(hào)為w.經(jīng)過此頂點(diǎn)后，tpt[u][v]變?yōu)樽钚≈担@就意味著u到v的最短路徑會(huì)經(jīng)過w.因此，利用遞歸調(diào)用的方式就能找出u到w的最短路徑和w到v的最短路徑.最后，將這兩個(gè)最短路徑相加就能得到u到v的最短路徑.

代碼4-1表示求最短路徑時(shí)額外計(jì)算所需附加信息的算法，以及計(jì)算實(shí)際路徑的函數(shù)源代碼.此代碼只額外利用O(|V|2)內(nèi)存就能計(jì)算最短路徑.

代碼4-1 Floyd算法的改進(jìn)算法

//頂點(diǎn)個(gè)數(shù)

int v;

//圖結(jié)構(gòu)的鄰接矩陣表示法

//tpt[u][v]=從u到v的邊線加權(quán)值.若沒有邊線，就代入極大值.

int tpt[MAX_V] [MAX_V];

//tpt[u][v]=u到v的最短路徑經(jīng)過的頂點(diǎn)中序號(hào)最大的頂點(diǎn)

//初始化為-1

int via [MAX_V] [MAX_V];

void floyd2(){

for(int i=0;i

memset(via, -1,sizeof(via));

for(int k= 0：k

for(int i=0;i

for(int j=0;j

if(tpt[i][j]> tpt[i][k]+ tpt[k][j]){

via[i][j]=k

tpt[i][j]= tpt[i][k]+ tpt[k][j]

}

}

//計(jì)算u到y(tǒng)的最短路徑,并保存到path

void reconstruct(int u, int v, vector& path){

//初始部分

if(via[u][v]==-1){

path.push _back(u);

if(u!=v) path.Push_ back(v);

}

else {

int w= via[u][v];

reconstruct(u, w, path)

path,pop_back(); // 因w重復(fù),故將其刪除.

reconstruct(w, v, path);

}

}

5 結(jié)束語(yǔ)

本研究的算法雖然對(duì)Floyd算法做了改進(jìn)，但并沒有Floyd算法靈活.Floyd算法的另一個(gè)著名應(yīng)用是，在無權(quán)圖中計(jì)算各頂點(diǎn)之間的到達(dá)可能性[5],也就是對(duì)所有成對(duì)頂點(diǎn)u、v確認(rèn)是否存在相連路徑.把Ck(u，v)的定義變換為，把0到k號(hào)頂點(diǎn)用作途經(jīng)點(diǎn)時(shí)，給出是否存在u到v的路徑，則有如下遞歸式.

Ck(u,v)=Ck-1(u,v)||(Ck-1(u,k)&&Ck-1))

這種表示法其實(shí)與Floyd算法完全相同，只是把求出最小值的運(yùn)算替換為or運(yùn)算，把相加運(yùn)算替換為and運(yùn)算.與從所有頂點(diǎn)起始進(jìn)行寬度優(yōu)先搜索時(shí)的時(shí)間復(fù)雜度相比，這種方法的時(shí)間復(fù)雜度并沒有什么提高.不過，F(xiàn)loyd算法的簡(jiǎn)潔性還是使其得到廣泛應(yīng)用.