多源最短路徑Floyd算法的分析與實現(xiàn)

摘要：本文比較詳細的介紹了多源最短路徑的Floyd算法設(shè)計思想，并使用C語言實現(xiàn)了該算法，并對該算法的時間復(fù)雜度進行了討論，在此基礎(chǔ)上使用Rational Quantify測試了該算法的實際時間復(fù)雜度。
 關(guān)鍵詞：最短路徑   Floyd算法   算法分析   GIS

Abstract: This paper introduces the thinking of the shortest path’s Floyd in great details, and implements the algorithm with C language. Also, the article analyses the time complexity of the algorithm and tests it with Rational Quantify.
Keywords: shortest path; algorithm Floyd; algorithm analysis; GIS

 1. 引言
 網(wǎng)絡(luò)分析作為GIS最主要的功能之一，在電子導(dǎo)航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計中發(fā)揮了重要的作用，而網(wǎng)絡(luò)分析中最基本、最關(guān)鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其它的度量，如時間、費用、線路容量等等。相應(yīng)地，最短路徑問題就成為最快路徑問題、最低費用問題等。對于單源點的最短路徑問題，一般采用經(jīng)典的最短路徑算法——Dijkstra算法，只是不同系統(tǒng)對Dijkstra算法采用了不同的實現(xiàn)方法。本文對多源路徑算法Floyd算法做了詳細的介紹，并編程實現(xiàn)了該算法，最后測試了該算法的性能。
 2. 多源路徑Floyd算法思路
 本算法采用鄰接矩陣存儲圖的網(wǎng)絡(luò)信息，在此用鄰接矩陣cost[MAX][MAX]來表示帶權(quán)有向圖，若從Vi到Vj有弧，則cost[i][j]值為弧(Vi，Vj)上的權(quán)值，否則為∞。從圖的鄰接矩陣cost出發(fā)，求圖中從Vi到Vj的最短路徑長度和結(jié)點序列。節(jié)點圖圖l的cost矩陣如圖2所示。

 如果從Vi到Vj存在弧，則從Vi到Vj存在一條長度為cost「i][j]的路徑，該路徑不一定是最短路徑，尚需進行n次試探。第一次判別(Vi，V1，)和(V1，Vj)，即判別(Vi，V1，Vj)是否存在，若存在，則比較(Vi，Vj)和(Vi，V1，，Vj)路徑，取其中最短路徑，作為從Vi到Vj的中間頂點不多于一個的最短路徑;第二次增加頂點V2，若(Vi……V2)和(V2……Vj)是當(dāng)前找到的中間結(jié)點個數(shù)不多于一個的最短路徑，則(Vi，……，V2，……，Vj)就有可能是從Vi到Vj的最短路徑。將它和已經(jīng)得到從Vi到Vj的中間頂點不多于一個的最短路徑相比較，從中選出長度較短者作為從Vi到Vj的中間頂點不多于二個的最短路徑;第三次再增加一個頂點V3，繼續(xù)進行試探，以此類推。經(jīng)過n次比較后，最后求得的一定是從Vi到Vj最短路徑。按此算法，可以同時求得各對頂點之間的最短路徑。
 由上所述，隨著試探時內(nèi)的不斷變化，遞推地產(chǎn)生一個n×n方陣序A0，A1，A2，……，Ak……，An記錄著試探的過程。
 其中:A0 [i] [j] =cost[i] [j]
 Ak[i][j]== min{Ak-1[i][j]，Ak-1[i][k]+Ak-1[k][j]}    1≤k≤n
 在計算公式中，A0[i][j]為初始值，A1[i][j]是從Vi到Vj的中間頂點個數(shù)不多于一個的最短路徑;Ak[i][j]是從Vi到Vj中間頂點個數(shù)不多于K個的最短路徑;An[i][j]是從Vi到Vj中間頂點個數(shù)不多于n-1個的最短路徑;即An[i][j]就是從Vi到Vj的最短路徑。在程序中，用數(shù)組C[i][j]來存放從頂點Vi到Vj的中間點。
 算法分兩部分：第一部分計算出最短路徑矩陣An和中間點矩陣C；第二部分根據(jù)矩陣An和C求出給定起點到終點的最短路徑值和最短路徑所經(jīng)過的中間點。
 
 2.1. 計算最短路徑矩陣和中間點矩陣
 
將網(wǎng)絡(luò)圖用表示各頂點間距離dij的相鄰矩陣D＝（dij）表達。若圖中不存在�。╥，j），則置dij＝M（M為足夠大的正數(shù)）。dij按下述情況確定：若自頂點i必須經(jīng)其他點才能回到i，則置dij＝M；否則，置dij＝0。構(gòu)造中間點矩陣C＝（cij），對所有i，j置cij＝i，以表示此時自頂點i至j的路徑均經(jīng)中間點i。 至k＝0。
第2本步思路是依次以頂點k（k＝1，2，……n）作為中間點，在當(dāng)前頂點i至j的距離dij和自頂點i經(jīng)中間點k至j的距離dik＋dkj中，取其小者作為新的最短路長，并將實現(xiàn)此最短路徑的中間點k記與cij。由于取最小，故若dik及dkj＝M，則dik＋dkj必步比dij小，故不做。又當(dāng)i＝k或j＝k時，即經(jīng)本點時，也不做。
置k＝k+1。對所有dik≠M的i≠k和dkj≠M的j≠k 置dij＝min{dij，dik＋dkj}。若dik＋dkj<dij，則置cij＝k。
第3步：若某dij<0，則存在長為負值的回路，這不可能，故算法中止。若k<n轉(zhuǎn)回2步。算法以k＝n，dij>0終止，此時的dij為所有i至所有j的最短路長。
使用3個嵌套循環(huán)語句即可實現(xiàn)迭代過程：（使用一維數(shù)組代替二維數(shù)組）
 
 2.2. 求出最短路徑
 
建立一個含有n個的一維向量p，以存放最短路。K＝1，p[k]＝i，p[k+1]＝j(luò)；
構(gòu)造最短路。將x＝cij，若x≠i且x≠j，說明x是i和j間的中間點，則將p之自n-1至k+1的諸元素依次后移一個標號，并將p[k+1]＝x，j＝x，轉(zhuǎn)回2步，否則k＝k+1。若p[k+1] ≠0，意為最短路尚未構(gòu)成，則i＝p[k]，j＝p[k+1]，轉(zhuǎn)回2步。否則轉(zhuǎn)3步。
終止。此時p之前k個元素就是最短路上的標號。流程圖如下圖：
 3. 算法復(fù)雜度分析
 考察算法第一部分：即求出最短路徑矩陣d和得到中間點矩陣c算法時間復(fù)雜度：
 T（n）＝O（n3），
 由于采用鄰接矩陣表示，所以空間復(fù)雜度為：
 S（n）＝O（n2）
 考慮算法的第二部分：最好的情況是p中的元素不需要移動，即i到j(luò)的最短路徑就是由i直接到j(luò)，此時復(fù)雜度為1，最壞的情況是最短路徑經(jīng)過所有的頂點，所以p中的元素移動1+2+3+……n-1次，所以平均時間復(fù)雜度為：
 T（n）＝O（n2）
 空間復(fù)雜度為：
 S（n）＝O（n）
 所以總的來考慮，該算法的時間復(fù)雜度為O（n3），空間復(fù)雜度為O（n2）
 由于該算法第一次將所有點對之間的最短路徑的值和最短路徑的路徑信息全部計算出來了，所以第二次在相同網(wǎng)絡(luò)圖形下進行最短路徑分析時只需用到算法的第二部分，此時的算法復(fù)雜度為O（n2），所以該算法比較適合需要重復(fù)計算點對之間的最短路徑。重復(fù)使用的次數(shù)越多，總的時間復(fù)雜度越趨近O（n2）。
  4. 算法實現(xiàn)與性能測試
 
 本算法測試采用Rational Quantify工具進行，Quantify是一款面向VB、VC、JAVA的函數(shù)級性能分析工具，它可以自動的檢測出影響程序運行的性能瓶頸，同時提供圖形化的分析表格，幫助程序員進行性能的分析與優(yōu)化。
 在性能優(yōu)化的過程中，一些程序員往往是憑著經(jīng)驗去分析自己所寫的代碼，找到性能瓶頸，這樣會面臨兩個問題：
 （1）程序員所找到的性能瓶頸的代碼很可能是自己認為不合理的算法，但在優(yōu)化的過程中大家都知道性能的優(yōu)化往往不是優(yōu)化算法不合理的，而是主要優(yōu)化占用時間最長的函數(shù)；
 （2）在一個大型的項目中，如何在成千上萬的代碼中找到性能瓶頸是一個最頭痛的問題，如果自己不了解所在的項目那就更無法下手。
 Quantify可以高效的發(fā)現(xiàn)問題，且不是通過代碼的檢查來發(fā)現(xiàn)問題則是關(guān)鍵，Quantify有以下幾個優(yōu)勢：
 ① 對當(dāng)前的開發(fā)影響特別的少，還集成在一些通用的開發(fā)工具中，大大的增強了使用的容易度，比如Visual Studio;
 
 ② 性能的顯示以圖形的方式進行，可以很直接的了解到性能所在的瓶頸；
 ③ 無需源代碼就可以對大多數(shù)的系統(tǒng)進行性能的分析；
 ④ 同時顯示的函數(shù)的信息非常的詳細，包含了調(diào)用的次數(shù)，時間等，還有相關(guān)的調(diào)用關(guān)系；
 ⑤ 在測試功能的同時，對性能進行分析，不需要額外的輔助代碼；
 本文中為了便于測試，采用隨機矩陣進行測試，隨機矩陣的對角線元素為零，其他元素是0至1000之間的隨機數(shù)。本例分別取了N＝{8，16，32，64，128，256，512}測試算法所耗CPU時間。

 測試結(jié)果如下表：
 問題規(guī)模
（頂點數(shù)） 函數(shù)Opti耗時
（毫秒） 函數(shù)f耗時
（毫秒） 總耗時
（毫秒） 理論耗時
（毫秒）
8 0.0099 0.0003 0.0102 0.0102
     16 0.0856 0.0002 0.0856 0.0816
     32 0.7199 0.0010 0.7209 0.6528
     64 5.8760 0.0011 5.8771 5.2224
     128 47.3333 0.0045 47.3378 41.7792
     256 379.5306 0.0063 379.5306 334.2336
     512 3036.8989 0.0681 3036.9770 2673.8688
 表1：測試結(jié)果表

5. 結(jié)論
 由測試結(jié)果圖表可知，隨著問題規(guī)模的增大，時間耗費以n3的增長，實際測試結(jié)果的增長速度略大于理論增長速度，但這種測試方式是理想的；但是有一定的局限性，在設(shè)計測試矩陣的時候是考慮了所有點對之間都有邊直接相連，而在實際情況中這是很少出現(xiàn)的，尤其是問題規(guī)模比較大的時候是不可能出現(xiàn)這種情況的，所以在實際情況中考慮到一個頂點的鄰接邊數(shù)目比較小，時間增長速度應(yīng)該比理論值小。
 對于函數(shù)f在測試過程中耗時總是小的原因，這是因為點和其他任何頂點都相連，所以一般只要經(jīng)過幾個頂點即可達到終點，所以p中需要移動元素的次數(shù)比較小，需要判斷的次數(shù)也比較小。

參考文獻
王凌 段江濤 王保保，GIS中最短路徑的算法研究與仿真,計算機仿真,
2005（1）：117 - 120.
許志海 魏峰遠，交通網(wǎng)絡(luò)中最短路徑算法分析與探討，河南理工大學(xué)學(xué)報，2005（1），74 - 78.司連法 王文靜，快速Dijkstra最短路徑優(yōu)化算法的 實現(xiàn)，測繪通報，2005（8）:15 - 18.
宋麗敏，最短路徑的編程實現(xiàn)，華北航天工業(yè)學(xué)院學(xué)報，2001（11）:25 - 27.
陸 鋒，最短路徑算法: 分類體系與研究進展[J ]，測繪學(xué)報, 2001, 30 (3): 270 - 275.
Benjamin F Zhan. Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures [J]. Journal of Geographic Information and Decision Analysis, 1998, 1 (1), 69 - 82.