一種基于最短優先的最短路徑算法的實現

薩賢春，辛 赟，陳憲東，楊 超

(1.西安科技大學，陜西 西安710054;2.陜西省測繪地理信息局，陜西西安710054)

一、引 言

路徑分析是GIS中網絡分析的重要組成部分，其中最短路徑算法作為路徑分析的主要研究內容，已被應用到諸如機器人運動設計(robot motion planning)、電網、高速公路建設、煤礦風網解算及計算機網絡路由等各個方面［1］。現有的最短路徑算法按照實現技術可分為標號算法與代數算法兩大類。其中標號算法使用比較廣泛，其代表的算法有最短優先搜索算法Dijikstra、Floyd等，代數方法有矩陣乘法等［2］。目前所公認的最好的求解最短路徑問題的方法是 1959年由 Dijkstra提出的標號法，即Dijikstra算法。本文從蟻群思想出發，通過不同的數據結構與標記方式，設計并實現了一種最短路徑求解的新算法。假設從起點開始放出一群螞蟻，始終是爬行過程中花費最少的一只在向前爬行，通過對每一次爬行過的節點和弧段進行標號的方法來確保該過程是最短優先搜索策略，即搜索到的路徑為最短路徑。

二、算法描述

廣度優先搜索屬于一種盲目搜索策略，是最簡便的圖的搜索算法之一，也是很多重要的圖的算法原型。本文所采用的方法就是基于一種廣度優先的最短優先搜索思想。

1.算法思想

在一個賦權無向圖G(V，E，W)中，已知起始節點s與終止節點d，在起始節點處放置一群螞蟻(ants)，使得其中始終是爬行過程中花費路徑值(mVal)最少的一只螞蟻在向前爬行(繁殖)，并對每只螞蟻爬行過的節點與弧段進行標記(isAnt)，若螞蟻在爬行的過程中遇到已經標記過的節點或弧段，則該螞蟻停止爬行并死亡(路徑死亡)。那么，所有螞蟻中最先爬到終止節點的，其爬過的路徑即為網絡G(V，E，W)中起始節點s到終止節點d的最短路徑。

2.數據結構

網絡中存儲的主要要素為網絡節點、網絡弧段和空間拓撲關系。節點與弧段是基礎要素，是組成網絡的物理要素，而空間拓撲關系描述的是它們之間的關系。圖的拓撲關系存儲采用節點與邊數據結構，在節點上附加記錄與之相連弧段的信息。與鄰矩陣的存儲方式相比，基于鄰近節點的拓撲關系存儲方法節省了內存，可用于規模較大的網絡分析。本文網絡中具體節點結構如下:

3.算法設計運行過程

采用本文所述路徑搜索策略的最優路徑算法流程如圖1所示。圖中路徑繁殖指的是:對原來的路徑向前擴展一個未標記過的弧段，路徑值增加該弧段的值。以s與d分別代表起點與終點，算法結束的條件為找到最短路徑或圖中的節點已經被永久地標記。

圖1 算法流程

以圖2為例，使用該算法求解從起點(29)到終點(6)的最短路徑。具體執行步驟如下:

1)標記起始節點29，初始化起始路徑為29—37、29—27、29—23、29—16，并標記弧段 29—37、29—27、29—23、29—16。

2)因為節點29已被標記過，因此路徑29—37、29—27在擴展時死亡。

3)對路徑列表中剩余的路徑進行擴展。在該網絡圖中首先繁殖路徑29—23。節點23未被標記，因此標記節點 23并擴展，即 29—23—17、29—23—22、29—23—30、29—16;現在最短路徑為 29—16，對其進行繁殖，即 29—16—14、29—16—17、29—16—9、29—23—22、29—23—17、29—23—30。其中29—23—22為最短繁殖，但由于23—22已經被標記過，因此該路徑死亡。同理由于16—14已被標記，29—16—14 死亡。

擴展當前路徑列表中的29—16—9，擴展后為29—16—9—7、29—16—9—10、29—16—9—2、29—16—17、29—23—17、29—23—30。依次類推，按照流程圖直到當前的最短路徑的末尾節點為終止節點為止。最后的最短路徑結果為 29—16—9—10—11—12—13—6，與dijikstra路徑算法結果一致。

圖2

三、算法分析

1.算法證明

定義1:對于有向圖G(V，E，W)，Adj(vi)表示節點vi的出度弧段集合，即有向圖中以vi為起點的弧段集合。由文獻［3］可知，在一般GIS的網絡圖中，Adj(vi)的個數一般為2～5。

結論1:A為在執行搜索的過程中產生的臨時路徑集合。存在 ai∈A，mVali為路徑集合 A{a1，a2，…，an}中最短路徑的路徑值。

結論2:對于路徑集合A，A中所有的路徑均為路徑的末尾節點至起始節點的最短路徑。

結論3:圖G(V，E，W)中從起始節點開始，每次進行路徑繁殖的始終是路徑集合中值mVal最短且路徑的尾節點vi?P未被標記過，因此最先到達終止節點的路徑即為最短路徑。

結論2的證明:在搜索過程中對于每一條路徑ai，其尾部節點到起始節點的距離di表示路徑ai的長度。由于在搜索過程中對擴展過的節點與弧段進行標記，若在搜索過程中某一路徑擴展時遇到的節點或弧段已被標記過，則說明至該節點或該弧段有比當前路徑更短的路徑，因此對該路徑擴展一定不能得到最短路徑，該路徑死亡。根據結論2，一旦搜索至終止節點，則可以確定最短路徑，結論3得證。

算法證明過程如下:P={s}，T=V－P，P為標記過的節點集合，T表示未標記過的節點集合。根據起始點s初始化起始路徑集合A;標記起始節點s，P={s}，T=V－P。

1)開始進入循環:對于路徑集合A{a1，a2，…，an}，若沒有從起點s至終點d路徑，則根據結論1有

2)對 A{a1，a2，…，an}中每一條路徑值 mValk，取長度最短的路徑ai為其路徑值mVal;其他路徑值大于min Val。判斷該最短路徑的末尾節點vik是否為終止節點d，若是，則找到最短路徑，搜索停止，否則進行步驟3)。

3)若路徑ai末端的節點vk∈P，則說明至該節點有比路徑ai更短的路徑，該路徑為非最短路徑，路徑死亡。若vk∈T，則標記vk，使vk∈P。

4)根據結論3，對路徑ai進行繁殖，設Adj(vk)中未被標記過的弧段有m個，則原來的ai被繁殖為m條新路徑，繁殖后的新路徑的路徑值mVal增加加入路徑弧段的值wkj，使用繁殖后的路徑和未進行繁殖的路徑更新路徑集合A，進入下一次循環，直到找到最短路徑或A的個數為0為止。

2.算法效率分析

設k為n次路徑集合中路徑個數的平均值，k的大小與網絡規模的大小有關。從根據起點初始化的路徑集合開始，每次對候選路徑集合求最短路徑采用的是冒泡排序的方式，它的時間復雜度為k2;每次對集合中的最短路徑至少向前擴展一個節點，擴展至所有節點n的時間復雜度為nk;每次對最短路徑擴展的時候，路徑末尾出度節點的個數k1約為2～5，那么對所有節點進行擴展的時間復雜度為nk1。因此，總的復雜度為O(nk2+nk+nk1)。

四、結束語

本文算法從蟻群思想出發，以最短優先搜索為基礎，在路徑搜索過程中采用對節點與弧段標號的方法確保每次進行繁殖的路徑為所有路徑中最短的，從而保證搜索過程中從起點開始的路徑中首先到達終點的為最短路徑。筆者在主頻為2.20 GHz、內存為2 GB、操作系統為Windows7的計算機上，使用C#對其運行效率進行了測試，結果見表1。

表1

與傳統的方法相比，該算法結構簡單，便于理解，執行效率也不遜色，有一定的實用性。同時，本算法也支持并行計算。

［1］嚴蔚敏，吳偉民.數據結構［M］.2版.北京:清華大學出版社，1997.

［2］陸鋒.最短路徑算法:分類體系與研究進展［J］.測繪學報，2001，30(3):269-275.

［3］夏松，韓用順.GIS中最短路徑算法的改進實現［J］.測繪通報，2004(9):40-42.

［4］王明中，謝劍英，陳應麟.一種新的Kth最短路徑搜索算法［J］.計算機工程與應用，2004(30):49-89.

［5］司連法，王文靜.快速Dijkstra最短路徑優化算法的實現［J］.測繪通報，2005(8):15-18.

［6］陳潔，陸鋒.交通網絡最短路徑標號算法的實現與效率分析［J］.中國圖象圖形學報，2005，10(9):1134-1138.

［7］王臣杰，毛海城，楊得志.圖的節點-弧段聯合結構表示法及其在GIS最優路徑選取中的應用［J］.測繪學報，2000，29(1):47-51.

［8］YUE Y.An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm［J］.Journal of Wuhan Technical University of Surveying and Mapping，1999，24(3):209-212.

［9］高松，陸鋒，段瀅瀅.一種基于雙向搜索的K則最優路徑算法［J］.武漢大學學報:信息科學版，2008，33(4):418-421.

［10］徐業昌，李樹祥，朱建民.基于地理信息系統的最短路徑搜索算法［J］.中國圖象圖形學報，1998，3(1):39-42.