基于Floyd算法的校園最短路徑問題分析與實(shí)現(xiàn)

嚴(yán)曉鳳，陸濟(jì)湘，唐雙平

(武漢理工大學(xué)理學(xué)院，湖北武漢 430070)

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，空間信息及其分析能力、處理能力也大大加強(qiáng)，搜索最短路徑已成為當(dāng)前研究的熱點(diǎn)問題。在ArcGIS軟件中有自帶的網(wǎng)絡(luò)分析模塊，具有分析矢量數(shù)據(jù)的功能。由于進(jìn)行分析的矢量數(shù)據(jù)必須具有拓?fù)潢P(guān)系，因此，在進(jìn)行網(wǎng)絡(luò)分析前，要先對相應(yīng)的矢量數(shù)據(jù)進(jìn)行拓?fù)浞治?，再用ArcGIS中的網(wǎng)絡(luò)分析工具創(chuàng)建幾何網(wǎng)絡(luò)并分析最佳路徑［1］。該方法既繁瑣又不易掌握。因此，筆者將以武漢理工大學(xué)南湖校區(qū)為例，研究求解最短路徑問題更簡便的方法，先對矢量圖進(jìn)行簡單處理，提取點(diǎn)要素和線要素的信息，再用先進(jìn)的Floyd算法對最短路徑問題進(jìn)行分析，并在Matlab中實(shí)現(xiàn)。在最短路徑問題中有很多算法需要進(jìn)行矩陣運(yùn)算，用C語言之類的高級編程語言實(shí)現(xiàn)這些算法比較繁瑣，編程也比較復(fù)雜，但Matlab則提供了許多矩陣運(yùn)算的高效函數(shù)，使得算法的實(shí)現(xiàn)方便了許多［2］。

1 ArcGIS中創(chuàng)建校園矢量圖

ArcGIS中創(chuàng)建矢量圖主要是在ArcMap中完成的，ArcMap是ArcGIS的3個用戶桌面組件之一，它能夠?qū)崿F(xiàn)對地圖進(jìn)行繪制、編輯及分析的操作，提供了基于地圖的所有功能。

對二維地圖進(jìn)行矢量化操作可分為幾個步驟:準(zhǔn)備地理數(shù)據(jù)、創(chuàng)建地理數(shù)據(jù)庫、地圖定位(地理配準(zhǔn))、要素矢量化和要素符號化等。在ArcGIS中創(chuàng)建的校園矢量化地圖如圖1所示。

圖1 校園矢量圖

ArcGIS中創(chuàng)建的校園地圖是基于實(shí)際位置及實(shí)際大小來完成的，從而可保證后期在該地圖上求解最短路徑問題的準(zhǔn)確性。

2 最短路徑及其算法

2.1 最短路徑的相關(guān)概念

對圖進(jìn)行存儲主要是指對圖中的頂點(diǎn)及邊的相關(guān)信息進(jìn)行存儲，圖中各個頂點(diǎn)之間為多對多的關(guān)系，因此，在實(shí)際應(yīng)用中，一般采用鄰接矩陣的存儲結(jié)構(gòu)。鄰接矩陣是通過一個矩陣來描述圖中頂點(diǎn)間的相關(guān)信息。若給定一個圖G=(V，E)，圖 G 的頂點(diǎn)集為 V(G)={v0，v1，v2，…，vn-1}，邊集為 E(G)={e0，e1，e2，…，en-1}，則圖 G的鄰接矩陣為以下的n階矩陣:

最短路徑問題有單源點(diǎn)最短路徑問題及全源點(diǎn)最短路徑問題。

已知給定的一個帶權(quán)有向圖 G=(V，E)，aij=(vi，vj)為 G 中的任一條弧，W(aij)=Wij為弧aij上的權(quán)，給定G中某個源點(diǎn)vs和目的點(diǎn)vt，設(shè)p為G中vs到vt的某條路徑，定義p的權(quán)W(p)為p中所有弧的權(quán)之和，即:

若圖G中vs到vt的一條路徑p1滿足條件:W(p1)=min{W(p)|p為從vs到vt的路徑}，則稱p1為vs到vt的最短路徑。對于圖G，求給定的源點(diǎn)vs到目標(biāo)點(diǎn)vt的最短路徑及最短距離問題即為單源點(diǎn)最短路徑問題。

若vi與vj分別為圖G中的任意節(jié)點(diǎn)，圖G中vi到vj的一條路徑p2滿足以下條件:W(p2)=min{W(p)|p為從vi到vj的路徑}，則稱p2為任意兩節(jié)點(diǎn)vi到vj的最短路徑，求任意兩節(jié)點(diǎn)vi到vj的最短路徑及最短距離問題即為全源點(diǎn)最短路徑問題。

2.2 最短路徑的基本算法

通過許多學(xué)者多年來在最短路徑問題中的研究，已經(jīng)發(fā)展了多種最短路徑算法，如文獻(xiàn)［3-7］所示，包括Dijkstra算法、Bellman-Ford算法、A*算法、Floyd-Warshall算法，其比較分析如表1所示。

表1 各種典型算法優(yōu)缺點(diǎn)的比較分析

通過表1中分析比較可知，由于A*算法中的收斂時(shí)間一般為指數(shù)級，因此求解最短路徑的問題中用的相對較少;而對于遺傳算法及蟻群算法［8］，它們的最終結(jié)果都會受其參數(shù)的影響，且算法比較復(fù)雜，不易編程實(shí)現(xiàn)。對于要在ArcGIS矢量化地圖的基礎(chǔ)上，對校園中各地點(diǎn)之間的最短路徑問題進(jìn)行求解，應(yīng)該采用Dijkstra算法或Floyd算法。比較這兩種算法，Dijkstra算法是求解單源點(diǎn)最短路徑問題，因而，需要重復(fù)執(zhí)行n次Dijkstra算法才能得到最終解，而Floyd算法可直接用于求解全源點(diǎn)最短路徑問題，顯而易見，F(xiàn)loyd算法的效率要高于Dijkstra算法。因此，根據(jù)以上各種典型算法的特點(diǎn)，決定采用Floyd算法在武漢理工大學(xué)南湖校區(qū)矢量化地圖的基礎(chǔ)上，求出校園中各地點(diǎn)之間的最短路徑及最短距離［9］。

3 Floyd算法

3.1 Floyd算法的基本思想

不妨將圖G中的頂點(diǎn)分別編號為0，1，2，…，n-1，令P表示頂點(diǎn)vi到頂點(diǎn)vj之間的一條路徑表示這條路徑的長度，在這條路徑P中，只將前m個頂點(diǎn)0，1，2，…，m-1作為中間節(jié)點(diǎn)。定義如下:

令Dm為一個N階矩陣，為其(i，j)元素，若圖G中每條弧的長度已知，則可以確定矩陣D0，通過迭代最終確定最短路徑長度的矩陣

3.2 Floyd算法的步驟

根據(jù)Floyd算法的基本思想，其實(shí)現(xiàn)步驟主要分為3步:

(1)定義初始的距離矩陣為H0=G，鄰接矩陣G如下:

(2)依據(jù)以下公式構(gòu)造矩陣Hk。

(3)當(dāng) Hk=Hk+1，終止算法;否則，重復(fù)步驟(2)。

以上步驟中，每次求解頂點(diǎn)vi到頂點(diǎn)vj的最短路徑時(shí)，都要進(jìn)行n次加法計(jì)算，且許多插入的中間節(jié)點(diǎn)vk明顯不能使當(dāng)前路徑長度變短;此外，要找到從頂點(diǎn)vi到頂點(diǎn)vj的最短路所包含的完整路徑，往往需要采用反向追蹤的方法進(jìn)行查找，直到搜索到 H0［i］［j］為止，這些都使得計(jì)算效率大大降低。因而采用簡化后的步驟:

(1)構(gòu)造初始距離矩陣H0及序號矩陣C0，矩陣的元素如下:

(2)構(gòu)造距離矩陣H0的迭代矩陣Hk及中間節(jié)點(diǎn)的序號矩陣Ck。

對于Hk［i］［j］，迭代中當(dāng)中間節(jié)點(diǎn)序號m 在1到 n 之間遞增，且 m≠i，m≠j時(shí)，若 Hk-1［i］［m］≥Hk［i］［j］或 Hk-1［m］［j］≥Hk［i］［j］，則表示插入節(jié)點(diǎn)vm后，當(dāng)前的路徑長度Hk-1［i］［j］不會變短，因此，不用再計(jì)算 Hk-1［i］［m］+Hk-1［m］［j］;若 Hk-1［i］［m］＜ Hk［i］［j］且 Hk-1［m］［j］＜Hk［i］［j］，則:

對于節(jié)點(diǎn)的序號矩陣 Ck，若 Hk［i］［j］=Hk-1［i］［m］+Hk-1［m］［j］，Hk［i］［j］＜ Hk-1［i］［j］，則記錄下節(jié)點(diǎn) vm，有 Ck［i］［j］={Ck-1［i］［m］，vm，Ck-1［m］［j］};否則，有 Ck［i］［j］=Ck-1［i］［j］。

(3)當(dāng)Hk=Hk+1時(shí)，終止算法;否則，重復(fù)步驟(2)。

3.3 Floyd算法的復(fù)雜度分析

對于原始的Floyd算法，當(dāng)對頂點(diǎn)vi到頂點(diǎn)vj的最短路徑 Hk［i］［j］進(jìn)行計(jì)算時(shí)，每次都需要對其第i行及第j列所對應(yīng)的元素進(jìn)行相加運(yùn)算，一共有n次加法運(yùn)算，且對于迭代的距離矩陣，其中共有n×n個元素，因此，算法的時(shí)間復(fù)雜度為o(n3)。

對簡化后的Floyd算法，當(dāng)對vi到vj的最短路徑 Hk［i］［j］進(jìn)行計(jì)算時(shí)，有 m≠i，m≠j，因此，對第i行及第j列所對應(yīng)的元素進(jìn)行相加運(yùn)算最多只需要進(jìn)行n-2次。此外，每次對 Hk［i］［j］計(jì)算前，都要對將要插入的節(jié)點(diǎn)vm先進(jìn)行路徑的長度比較，若 Hk-1［i］［m］≥Hk［i］［j］或Hk-1［m］［j］≥Hk［i］［j］，則表示插入節(jié)點(diǎn) vm后，當(dāng)前的路徑長度 Hk-1［i］［j］不會變短，因此，不用繼續(xù)計(jì)算 Hk-1［i］［m］+Hk-1［m］［j］;若第 i行或第j列所對應(yīng)的元素都不小于 Hk-1［i］［j］，則可以直接得出 Hk［i］［j］=Hk-1［i］［j］，此時(shí)加法運(yùn)算的時(shí)間復(fù)雜度為0。因此，對vi到vj的最短路徑 Hk［i］［j］進(jìn)行計(jì)算時(shí)，計(jì)算量為 0 ～ n-2次，是隨機(jī)變量，令其為Y，假設(shè)Y在0～n-2之間的取值具有相等的可能性，則Y的數(shù)學(xué)期望為，加法的計(jì)算量即為，而對于迭代的距離矩陣，其中共有n×n個元素。因此，用簡化后的Floyd算法使時(shí)間復(fù)雜度大大降低，為

3.4 Matlab中最短路徑算法的實(shí)現(xiàn)

對圖1提取線路的交點(diǎn)，再對它們建立點(diǎn)圖層并編號，得到的校園線路圖如圖2所示。

圖2 校園線路圖

圖2中:v1為校園大門，v2為教學(xué)樓2，v3為主教學(xué)樓，v4為圖書館，v5為理學(xué)院，v6為食堂2，v7為化學(xué)樓，v8為學(xué)生公寓1，v9為學(xué)生公寓2。

從點(diǎn)和線圖層中提取節(jié)點(diǎn)及弧段的信息，創(chuàng)建鄰接矩陣G如下:

矩陣 G 中的元素 dij(i，j=1，2，…，9)為頂點(diǎn) vi到頂點(diǎn)vj的距離，其中dij=∞為兩頂點(diǎn)間無路徑。

在Matlab運(yùn)行程序的過程中，由于∞在計(jì)算機(jī)中無法進(jìn)行計(jì)算，姑且將其定為100000000000000來計(jì)算，由于相對于其他的數(shù)據(jù)，100000000000000是比較大的，因此，這樣改變并不會對程序運(yùn)行后結(jié)果的準(zhǔn)確性產(chǎn)生影響。程序的部分代碼如下:

采用Matlab語言編程實(shí)現(xiàn)Floyd算法可求得最短路徑，各頂點(diǎn)之間的最短距離如表2所示。

表2 各頂點(diǎn)之間的最短距離 m

4 結(jié)論

通過簡化的Floyd算法，較好地解決了網(wǎng)絡(luò)圖中的任意兩頂點(diǎn)的最短路徑問題，采用簡化后的Floyd算法進(jìn)行計(jì)算，可以加快迭代速度，省去大量多余的操作，大大減少運(yùn)行的時(shí)間;此外，由于在計(jì)算節(jié)點(diǎn)間路徑長度之前先對其進(jìn)行了大小的比較，對于那些與給定節(jié)點(diǎn)對不直接相連接的插入節(jié)點(diǎn)，它們不能使當(dāng)前的路徑變短，以及那些與節(jié)點(diǎn)對直接相連的且其路徑長度比節(jié)點(diǎn)對路徑要長的插入節(jié)點(diǎn)，在算法的過程當(dāng)中并沒有參與計(jì)算，因此，計(jì)算量大大減少了。

此外，在求解最短路徑的過程中，引入了序號矩陣用來記錄使兩頂點(diǎn)間的路徑長度變短的中間節(jié)點(diǎn)序號，從而使得求解最短路徑問題的過程更直觀、方便。通過Matlab編程語言對簡化后的Floyd算法求解最短路徑問題，操作簡單，且效果較好。

［1］湯國安，楊昕.ArcGIS地理信息系統(tǒng)空間分析實(shí)驗(yàn)教程［M］.北京:科學(xué)出版社，2006:19-65.

［2］王沫然.Matlab與科學(xué)計(jì)算機(jī)［M］.北京:電子工業(yè)出版社，2004:16-89.

［3］許志海，魏峰遠(yuǎn).交通網(wǎng)絡(luò)中最短路徑算法分析與探討［J］.河南理工大學(xué)學(xué)報(bào)，2005(1):74-78.

［4］榮瑋.基于道路網(wǎng)的最短路徑算法的研究與實(shí)現(xiàn)［D］.武漢:武漢理工大學(xué)圖書館，2005.

［5］BENJAMIN F Z.Three fastest shortest path algorithms on real road networks:data structures and procedures［J］.Journal of Geographic Information and Decision Analysis，1998(1):69-82.

［6］JI X Y.Models and algorithm for stochastic shortest path problem［J］.Applied Mathematics and Computation，2005，70(2):503-514.

［7］周先曙.最短路徑問題及其解法研究［J］.電腦知識與技術(shù)，2010(6):1403-1412.

［8］夏蘭.基于蟻群算法的交通地理最佳路徑的研究［D］.武漢:武漢理工大學(xué)圖書館，2009.

［9］陸濟(jì)湘，南良改.一種新的基于重采樣的曲線重建算法［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2009，31(6):861-864.

［10］WEI D C.Implementation of route selection function based on improved floyd algorithm［C］//Proceedings 2010 WASE International Conference on Information Engineering.［S.l.］:［s.n］，2010:223-227.

［11］WEI D C.An optimized floyd algorithm for the shortest path problem［J］.Journal of Networks，2010，5(12):1496-1504.