摘要：由一道數(shù)學(xué)建模題“開(kāi)封市旅游路線問(wèn)題”而引發(fā)的關(guān)于Floyd-Warshall算法求任意兩點(diǎn)間最短路徑的思考，通過(guò)圖解描述了算法的核心過(guò)程并針對(duì)虛擬案例用C++實(shí)現(xiàn)，最后做了算法思想的引申思考。

關(guān)鍵字：Floyd-Warshall；最短路徑；算法思想引申；旅游路線；APSP

中圖分類號(hào)：TP311.11 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 (2012) 09-0000-02

一、引言

伴隨著高科技的日新月異，計(jì)算機(jī)技術(shù)被應(yīng)用到各個(gè)領(lǐng)域，因特網(wǎng)的迅速普及使計(jì)算機(jī)進(jìn)一步融入到我們的日常生活中。在這個(gè)信息爆炸的e時(shí)代，時(shí)間顯的尤為寶貴，我們不自覺(jué)的應(yīng)用著各種統(tǒng)籌原理和各式各樣的“算法”來(lái)爭(zhēng)取時(shí)間，效率至上成了很多個(gè)人和組織所追求的意識(shí)，就算在旅游休閑時(shí)，人們也會(huì)想要在有限的資源條件下比別人多賞玩一個(gè)“景點(diǎn)”，當(dāng)然我們追求的不僅僅是多，而且是快。下面就讓我們來(lái)探討Floyd-Warshall算法如何幫助我們解決“旅游路線”問(wèn)題——實(shí)現(xiàn)任意兩點(diǎn)“最短路徑”！

二、算法描述和圖解

Floyd-Warshall算法是圖論中的一個(gè)算法，專業(yè)的講是尋找給定的帶權(quán)圖或有向網(wǎng)G=（V，E）上每對(duì)頂點(diǎn)間最短路徑的算法，即APSP(All Pairs Shortest Paths)。該算法運(yùn)用動(dòng)態(tài)規(guī)劃思想，框架清晰，不包含復(fù)雜數(shù)據(jù)結(jié)構(gòu)，三重嵌套For循環(huán)結(jié)構(gòu)緊湊，易于實(shí)現(xiàn)，提高了運(yùn)算效率，邊權(quán)可正可負(fù)。缺點(diǎn)是時(shí)間復(fù)雜度較高（O( )），不適合計(jì)算大量數(shù)據(jù)。但對(duì)于中等規(guī)模的輸入圖仍然相當(dāng)實(shí)用。

任意兩點(diǎn)最短距離有三種情況：

（1）兩點(diǎn)直達(dá)。例如圖最短路徑：V->X，路徑長(zhǎng)度：3

（2）通過(guò)一個(gè)中間點(diǎn)。例如圖最短路徑：V->X->U，路徑長(zhǎng)度：7

（3）通過(guò)兩個(gè)及以上點(diǎn)。例如圖最短路徑：V->X->U->W，路徑長(zhǎng)度：8

算法過(guò)程是用一個(gè)矩陣d[][]記錄每一對(duì)頂點(diǎn)的最短距離，當(dāng)i等于j時(shí)，d[i][j]賦初值為0，當(dāng)i和j不可達(dá)時(shí)，d[i][j]賦初值為一個(gè)大數(shù)，表示無(wú)窮。初始化后，依次掃描每一個(gè)點(diǎn)，并以其為基點(diǎn)再遍歷每一對(duì)頂點(diǎn)的權(quán)值d[][]，看是否可過(guò)該基點(diǎn)讓這對(duì)頂點(diǎn)間的距離更小。

第一種情況：在初始化的時(shí)候已經(jīng)完成。

第二種情況：對(duì)于每一對(duì)頂點(diǎn)，遍歷所有其它頂點(diǎn)，看是否可以通過(guò)一個(gè)頂點(diǎn)讓這對(duì)頂點(diǎn)距離更短，相當(dāng)于遍歷了圖中所有的三角形。

第三種情況：如右圖的六邊形，可先找一點(diǎn)（Y，則=7），右圖就變成了五邊形問(wèn)題（V，X，U，W，Z），再找一點(diǎn)（X，則=7），右圖就變成了四邊形問(wèn)題（V，U，W，Z），再找一點(diǎn)（U，則=8），右圖就變成了三角形（V，W，Z）問(wèn)題。也就演變成了第二種情況。并且不管先找到哪個(gè)點(diǎn)，總可以把n邊形問(wèn)題轉(zhuǎn)化成（n-1）邊形問(wèn)題，最終變成三角形問(wèn)題。

綜合上述三種情況，令 為從頂點(diǎn)i到頂點(diǎn)j且滿足所有中間頂點(diǎn)皆屬于集合{1，2，…，k}的一條最短路徑的權(quán)值， 為有向邊（i，j）的權(quán)，得出如下遞歸表達(dá)式：

三、C++核心代碼

#define NUM 100

#define INFINITY 32767 //表示權(quán)值的正無(wú)窮

typedef struct {

char vertex[NUM]； //頂點(diǎn)集

int edges[NUM][NUM]； //存儲(chǔ)有向網(wǎng)的鄰接矩陣

int vexnum；//點(diǎn)的數(shù)目

intarcnum； //弧的數(shù)目

}DirectedNet；//有向網(wǎng)

//初始化

void InitializeDN(DirectedNet DN){//輸入點(diǎn)數(shù)、弧數(shù)和點(diǎn)，依照上述“算法過(guò)程”進(jìn)行初始化 }

//Floyd算法核心

void Floyd(int distance[][NUM]，int path[][NUM]，DirectedNet DN) {

int i，j，k；

for (i=0；i

for (j=0；j

distance[i][j]=DN.edges[i][j]；

path[i][j]=1；

}

}

for (k=0；k

for (i=0；i

for (j=0；j

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

distance[i][j]=distance[i][k]+distance[k][j]；

path[i][j]=k；

}//用數(shù)組distance[i][j]來(lái)記錄i，j之間的最短距離，對(duì)所有的k值從1到n

} //計(jì)算distance[i][k]+distance[k][j]的值，修正任意兩點(diǎn)之間的最短距離

} //若小于distance[i][j]，則distance[i][j]= distance[i][k]+distance[k][j]

} //否則distance[i][j]的值不變。每計(jì)算一次都用path[i][j]記錄經(jīng)過(guò)的路徑點(diǎn)k

}

//遞歸輸出路徑點(diǎn)

void PathPoint(int path[][NUM]，int i，int j，DirectedNet DN) {

int k=path[i][j]；

if (k==1) { return；}

PathPoint(path，i，k，DN)；

printf(\"%c->\"，DN.vertex[k])；

PathPoint(path，k，j，DN)；

}

//輸出最短路徑及路徑長(zhǎng)度

void OutputPath(int distance[][NUM]，int path[][NUM]，DirectedNet DN) {

int i，j；

for (i=0；i

for (j=0；j

if (distance[i][j]==INFINITY) {

continue；//若要輸出無(wú)最短路徑信息，只需要注釋本行，取消注釋下一行

//printf(\"從 %c 到 %c 沒(méi)有路徑\\"，DN.vertex[i]，DN.vertex[j])；

}

else {if(i!=j){

printf(\"從 %c 到 %c 最短路徑長(zhǎng)度為%d\路徑\"，DN.vertex[i]，DN.vertex[j]，distance[i][j])；

cout<\"；

PathPoint(path，i，j，DN)；

cout<

}}}}}

算法描述中“六邊形”的任意兩點(diǎn)最短路徑運(yùn)行結(jié)果：

四、算法思想引申思考

當(dāng)問(wèn)題變復(fù)雜，不再是單純的類似“旅游問(wèn)題”的任意兩點(diǎn)最短路徑問(wèn)題，而是變?yōu)椤白顑?yōu)解”的問(wèn)題時(shí)，還是以“旅游問(wèn)題”為案例，在存有帶權(quán)矩陣的結(jié)構(gòu)體中加入諸如路費(fèi)（int spend）甚至更多的屬性，這時(shí)問(wèn)題將變?yōu)閷ふ胰我鈨牲c(diǎn)間“性價(jià)比”最高的路徑，并且在最短路徑算法基礎(chǔ)上又加入了貪心算法思想，如果再加入時(shí)間（double time）等屬性，那么問(wèn)題將逐漸演變成一個(gè)需要仔細(xì)規(guī)劃的Project，這也是現(xiàn)實(shí)中我們更可能面臨的問(wèn)題。所以Floyd算法以及算法思想引申在現(xiàn)實(shí)生活中有廣泛的應(yīng)用，能給我們帶來(lái)很多益處，值得仔細(xì)研究和進(jìn)一步思考。

參考文獻(xiàn)：

[1]科曼（Cormen，T.H.）.算法導(dǎo)論[M].潘金貴.北京:機(jī)械工業(yè)出版社，2009，6

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版[M].北京:清華大學(xué)出版社，2007

[3]沈云付.ACM/ICPC程序設(shè)計(jì)與分析（C++實(shí)現(xiàn)）[M].北京:清華大學(xué)出版社，2010，7

[作者簡(jiǎn)介]王志龍（1990-），男，山東青島人，河南大學(xué)2009級(jí)計(jì)算機(jī)與信息工程學(xué)院本科生，專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（軟件工程方向）。