Floyd-Warshall算法在現(xiàn)實(shí)生活中的應(yīng)用及算法思想引申
2012-12-31 00:00:00王志龍
計(jì)算機(jī)光盤軟件與應(yīng)用 2012年9期
摘要：由一道數(shù)學(xué)建模題“開封市旅游路線問題”而引發(fā)的關(guān)于Floyd-Warshall算法求任意兩點(diǎn)間最短路徑的思考，通過圖解描述了算法的核心過程并針對虛擬案例用C++實(shí)現(xiàn)，最后做了算法思想的引申思考。
關(guān)鍵字：Floyd-Warshall；最短路徑；算法思想引申；旅游路線；APSP
中圖分類號：TP311.11 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 (2012) 09-0000-02
一、引言
伴隨著高科技的日新月異，計(jì)算機(jī)技術(shù)被應(yīng)用到各個(gè)領(lǐng)域，因特網(wǎng)的迅速普及使計(jì)算機(jī)進(jìn)一步融入到我們的日常生活中。在這個(gè)信息爆炸的e時(shí)代，時(shí)間顯的尤為寶貴，我們不自覺的應(yīng)用著各種統(tǒng)籌原理和各式各樣的“算法”來爭取時(shí)間，效率至上成了很多個(gè)人和組織所追求的意識，就算在旅游休閑時(shí)，人們也會想要在有限的資源條件下比別人多賞玩一個(gè)“景點(diǎn)”，當(dāng)然我們追求的不僅僅是多，而且是快。下面就讓我們來探討Floyd-Warshall算法如何幫助我們解決“旅游路線”問題——實(shí)現(xiàn)任意兩點(diǎn)“最短路徑”！
二、算法描述和圖解
Floyd-Warshall算法是圖論中的一個(gè)算法，專業(yè)的講是尋找給定的帶權(quán)圖或有向網(wǎng)G=（V，E）上每對頂點(diǎn)間最短路徑的算法，即APSP(All Pairs Shortest Paths)。該算法運(yùn)用動態(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ù)。但對于中等規(guī)模的輸入圖仍然相當(dāng)實(shí)用。
任意兩點(diǎn)最短距離有三種情況：
（1）兩點(diǎn)直達(dá)。例如圖
（2）通過一個(gè)中間點(diǎn)。例如圖
（3）通過兩個(gè)及以上點(diǎn)。例如圖
算法過程是用一個(gè)矩陣d[][]記錄每一對頂點(diǎn)的最短距離，當(dāng)i等于j時(shí)，d[i][j]賦初值為0，當(dāng)i和j不可達(dá)時(shí)，d[i][j]賦初值為一個(gè)大數(shù)，表示無窮。初始化后，依次掃描每一個(gè)點(diǎn)，并以其為基點(diǎn)再遍歷每一對頂點(diǎn)的權(quán)值d[][]，看是否可過該基點(diǎn)讓這對頂點(diǎn)間的距離更小。
第一種情況：在初始化的時(shí)候已經(jīng)完成。
第二種情況：對于每一對頂點(diǎn)，遍歷所有其它頂點(diǎn)，看是否可以通過一個(gè)頂點(diǎn)讓這對頂點(diǎn)距離更短，相當(dāng)于遍歷了圖中所有的三角形。
第三種情況：如右圖的六邊形，可先找一點(diǎn)（Y，則
綜合上述三種情況，令 為從頂點(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)值的正無窮
typedef struct {
char vertex[NUM]； //頂點(diǎn)集
int edges[NUM][NUM]； //存儲有向網(wǎng)的鄰接矩陣
int vexnum；//點(diǎn)的數(shù)目
intarcnum； //弧的數(shù)目
}DirectedNet；//有向網(wǎng)
//初始化
void InitializeDN(DirectedNet DN){//輸入點(diǎn)數(shù)、弧數(shù)和點(diǎn)，依照上述“算法過程”進(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]來記錄i，j之間的最短距離，對所有的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)過的路徑點(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)； } //輸出最短路徑及路徑長度 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；//若要輸出無最短路徑信息，只需要注釋本行，取消注釋下一行 //printf(\"從 %c 到 %c 沒有路徑\\"，DN.vertex[i]，DN.vertex[j])； } else {if(i!=j){ printf(\"從 %c 到 %c 最短路徑長度為%d\路徑\"，DN.vertex[i]，DN.vertex[j]，distance[i][j])； cout< PathPoint(path，i，j，DN)； cout< }}}}} 算法描述中“六邊形”的任意兩點(diǎn)最短路徑運(yùn)行結(jié)果： 四、算法思想引申思考 當(dāng)問題變復(fù)雜，不再是單純的類似“旅游問題”的任意兩點(diǎn)最短路徑問題，而是變?yōu)椤白顑?yōu)解”的問題時(shí)，還是以“旅游問題”為案例，在存有帶權(quán)矩陣的結(jié)構(gòu)體中加入諸如路費(fèi)（int spend）甚至更多的屬性，這時(shí)問題將變?yōu)閷ふ胰我鈨牲c(diǎn)間“性價(jià)比”最高的路徑，并且在最短路徑算法基礎(chǔ)上又加入了貪心算法思想，如果再加入時(shí)間（double time）等屬性，那么問題將逐漸演變成一個(gè)需要仔細(xì)規(guī)劃的Project，這也是現(xiàn)實(shí)中我們更可能面臨的問題。所以Floyd算法以及算法思想引申在現(xiàn)實(shí)生活中有廣泛的應(yīng)用，能給我們帶來很多益處，值得仔細(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語言版[M].北京:清華大學(xué)出版社，2007 [3]沈云付.ACM/ICPC程序設(shè)計(jì)與分析（C++實(shí)現(xiàn)）[M].北京:清華大學(xué)出版社，2010，7 [作者簡介]王志龍（1990-），男，山東青島人，河南大學(xué)2009級計(jì)算機(jī)與信息工程學(xué)院本科生，專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（軟件工程方向）。
