邱曉鵬，王麗君

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

0 引言

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

1 Floyd算法分析

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

假設(shè)有連接兩個頂點(diǎn)u和v的路徑.此路徑肯定會經(jīng)過起點(diǎn)u和終點(diǎn)v，此外還會經(jīng)過其他頂點(diǎn).比如，沒有直接連接u和v的路徑，或者經(jīng)過其他頂點(diǎn)的路徑比直接連接的路徑更短，此時就會經(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)記法時，最終想得到的結(jié)果值是將整個頂點(diǎn)的集合V都用作途經(jīng)點(diǎn)的DV(u,v).連接兩個頂點(diǎn)的邊線中,最短邊線的長度w(u,v)等于D{}(u,v).

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

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

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

圖1 拓?fù)鋱D

1.2 Floyd算法的原型

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

遞歸式中，Ck的所有值只依賴于Ck-1，所以利用選代動態(tài)規(guī)劃法就非常容易求解.代碼1-1是實(shí)現(xiàn)這種方法的代碼.此代碼中，Ck(u,v)的值會保存到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]);

}

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

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

Floyd最短路徑算法在此基礎(chǔ)上更進(jìn)一步，在不使用額外數(shù)組的前提下，在保存圖結(jié)構(gòu)加權(quán)值的鄰接矩陣中計算遞歸式的結(jié)果值.利用滑動窗口就能把此代碼的內(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使用過的遞歸式中，為了計算出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個頂點(diǎn)用作途經(jīng)點(diǎn)的從u到k的最小長度；2、Ck(u,k)=把起點(diǎn)到第k個頂點(diǎn)用作途經(jīng)點(diǎn)的從u到k的最小長度.

可以確定起點(diǎn)或終點(diǎn)是第k個頂點(diǎn)時，把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中計算最短距離.此算法的時間復(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í)際問題時，會發(fā)現(xiàn)該算法的執(zhí)行時間只能勉強(qiáng)達(dá)到時間限制要求.對于這種情況，可以在不改變時間復(fù)雜度的前提下，依然能對算法進(jìn)行優(yōu)化，那就是在第二個for語句之后，確認(rèn)從i到k的路徑是否實(shí)際存在.如果從i到k的路徑不存在，就沒有必要對j執(zhí)行for語句.這樣會大大降低了運(yùn)算時間，巧妙地優(yōu)化了Floyd算法.

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

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

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

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

//頂點(diǎn)個數(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)中序號最大的頂點(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]

}

}

//計算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é)束語

本研究的算法雖然對Floyd算法做了改進(jìn)，但并沒有Floyd算法靈活.Floyd算法的另一個著名應(yīng)用是，在無權(quán)圖中計算各頂點(diǎn)之間的到達(dá)可能性[5],也就是對所有成對頂點(diǎn)u、v確認(rèn)是否存在相連路徑.把Ck(u，v)的定義變換為，把0到k號頂點(diǎn)用作途經(jīng)點(diǎn)時，給出是否存在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)先搜索時的時間復(fù)雜度相比，這種方法的時間復(fù)雜度并沒有什么提高.不過，F(xiàn)loyd算法的簡潔性還是使其得到廣泛應(yīng)用.