基于公交網絡的最短路徑算法的分析及對比

摘要：路徑分析是GIS最基本的分析功能，在公交網絡方面有著廣泛的應用。而最短路徑分析是地理信息系統(GIS)中網絡分析的一項重要功能．等價于圖論中的節點間求解最短路徑問題.在GIS應用的各個方面都有著很重要的地位。對于最短路徑的研究也一直沒有停止。對地理網絡進行地理分析和建模．實現最短路徑算法已經有大量論文討論，但是專門針對公交網絡的最短路徑算法則鮮有研究.本文在總結公交網絡特點的基礎上，引入了“搜尋”算法來計算公共交通系統的最優路徑。最后用一個簡化的例子來說明了這種算法的算法流程，對這種算法以及經典的Dijstra算法做了幾點比較，無論在空間復雜度還是時間復雜度方面都優于Dijstra算法。

關鍵詞：公交網絡最短路徑Dijkstra算法“搜尋”算法

0 引言

尋找兩頂點間的最短路徑的算法很多，目前應用最廣泛的算法是迪杰斯特拉1959年提出的Dijkstra算法。它不僅可求出從始點到終點的最短路徑，而且最后得到的實際上是始點到各頂點的最短路徑[1]。該算法直觀、可靠，是在嚴格基于圖論的條件下提出的，具有很好的適用性。但在實際應用中該算法存在數據冗余較多、時間復雜度較大等不盡如人意的方面，為了提高運算速度和節約對內存的開銷，人們研究提出了多種改良措施，如基于Dijkstra算法的優化算法—鄰接結點算法[2]等，但當算法應用到具體領域的最短路徑搜索時，還應該考慮到實際網絡的特征對算法進行改進和優化[3]。

因此，將現階段應用最廣泛的最短路徑算法在公交網絡的背景下做一下對比和分析，從而經過研究和探討，找出適用于公交網絡背景下的最短路徑算法是具有實際意義和應用價值的。本文就是在公交網絡的背景下對比和分析了幾種最短路徑算法的特點，最后找到了適用算法。

1 對Dijkstra算法的局限性分析

對公交線路來說，Dijkstra算法所采用的數據結構及其實現方法總體上說是比較復雜的，難以應付公交線路的網絡拓撲中的復雜性。主要表現如下：

①數據結構復雜。公交線路網絡很難用現有的數據結構加以完整的表示。如果采用現有算法分析，其建立的公交線路網絡的數據結構模型將非常復雜。

②算法時間長。以Dijkstra算法來計算公交路線最短路徑，算法采用的鄰接矩陣存儲圖的拓撲。一個有n個結點的圖，算法需要建立一個n*n的的矩陣，用以存儲結點之間的弧段的權值。其時間復雜度達到了O(n^2)。事實上，在實際的網絡中，結點的最大出度都不會超過10個，絕大多數的結點的連通都在2到6之間。設網絡中結點的最大鄰接點數為m，則每個結點只與網絡中所有n個結點中的最多m個連通。矩陣中其余的n-m個單元都是不連通的，其權值為∞。網絡結點n越大，則數據的冗余越大。當n很大時，即n>>m，會有：

(n-m)*n>>m*n

很明顯，在大數據量的情況下，計算速度會慢得讓人難以忍受。而系統設計中要求公交轉車的查詢必須在較短的時間內完成。

所以有必要使用一種改進算法，可以改進數據的冗余，降低系統資源的消耗，提高算法的運行速度，同時盡可能的保持數據結構的直觀性。于是引進Dijkstra算法的優化算法—搜尋算法。

2 “搜尋”算法

2.1 “搜尋”算法的基本思想

“搜尋”算法是綜合應用了鏈表結構和廣度優先搜索算法的一種類似于“點擴散”的算法，該算法從指定點開始逐漸蔓延到周邊鄰接點，直至找到另一指定點為止，所以該算法被形象地稱之為“搜尋”。

2.2 “搜尋”算法的實現

2.2.1 算法實現步驟

①創建三個數組，分別記錄從Di到其他各頂點的最少換乘次數，最短路徑中的前一個站點ID(用來記錄路徑通過的頂點)以及最短路徑長度(“站地”)。

②從鄰接表中讀出和Di有邊相連接的所有結點，將這些結點ID對應的LONG+1。PRO設為i，DIST設為兩站之間直達的最短距離(“站地”)。我們將這個從一個點出發對其他有關聯點的記錄進行賦值的做法形象地稱為“搜尋”。

③如果DIST中Dj對應的點已經被賦值，那么算法結束。

④對所有LONG值為1的站點，都重復②的過程，不過只對三個數組沒有賦值過的進行。

⑤重復步驟③。

⑥重復步驟④以及③的判斷。

2.2.2數據實驗

以圖1所示公交網絡為例，計算從站點1到站點7 的最優路徑:

圖中圓內數字代表站點，箭頭表示直達車的方向，邊上的數字表示兩站相距的“站數”。算法流程如下：從左到右通過4步得出結果，其中涂上陰影的圓是每一步中被搜尋的點，每個被計算的點旁邊的三列數字從上到下代表結點被賦予的LONG、PRO、DIST值，凡是被賦值的點都已經得出最優路徑了。

①初始化，讀入拓撲數據文件，建立相關的鄰接表并創建數組。

②從鄰接表中讀出和V1有邊連接的所有結點，即V2，將V2對應的LONG設為1，PRO設為1，DIST設為V1到V2的權值:5，具體見下圖1：

③對LONG值為1的站點重復②的過程，因為LONG值為1的站點只有2號，那么搜尋2號，即4號、5號站點被引燃。因為1號站點之前已經被賦予了相關值，所以不予考慮。此時4號、5號站點的LONG值升為2，PRO值為當前邊的起始點即2號站點，由于從1號站點到4號站點“站地”數僅有5+4=9，而從1號站點到5號站點“站地”數卻有5+5=10，所以DIST取從1號站點經2號站點到4號站點的“站地”數：9站。此時DIST中7號站點未被賦值。具體見下圖2：

④重復進行上述步驟，我們可以得出最終結果：具體見下圖3：

⑤對LONG值為4的站點重復（2）的過程，因為LONG值為4的站點只有6號，那么搜尋6號，即7號站點被引燃。此時目標點已尋到，所以從1號站點到7號站點的最短路徑為：1號站點—2號站點—5號站點—6號站點—7號站點；總的“站地”數為：24站；總共經過了5次換乘。算例結束。

2.2.3 “搜尋”算法和Dijkstra算法的比較

如前述：Dijkstra算法是O(n^2 )的復雜度，而“搜尋”算法相當于遍歷n的有限次的所有結點，所以其算法復雜度為O(n)。如果求所有兩兩站點間的最短路徑，Dijkstra是O(n^3)的復雜度，而搜尋算法是O(n^2)。此外，在專業的公交領域中，以廣度優先搜索算法為內核的“搜尋”算法比嚴格地基于圖論的Dijkstra算法更具有實際意義和可行性，因此，在基于公交網絡的最短路徑的對比中，“搜尋”算法可以算做一個比較好的選擇。

3 結論與展望

公交網絡是一個復雜的網絡系統，本文只是簡單地對比了2種基于不同應用核心的最短路徑算法的優劣，而人們在選擇公交出行線路時考慮的因素很多如：出行耗時是否最少，換乘次數是否最少，是否方便，耗費是否最少，線路是否最短等等，面對如此多要考慮的因素，有時就很難做準確的判斷，很明顯，目前已有的最短路徑算法還遠未滿足人們多樣化地出行方式，因此，最“優”路徑這個概念將會是現在乃至未來核心算法的研究對象。

另外，公交網絡加上人的因素就可以視為一個復雜系統，既是系統就可以應用系統工程概念來研究它，比如可以應用“混沌”理論和“耗散”理論來研究其特性，也可以應用“熵”理論來研究其反饋，這都是我們在研究中需要注意的。

參考文獻：

[1]夏松，韓用信.GIS中最短路徑算法的改進實現[J].測繪通報，2004，(9)：40~42.

[2]李寧寧，劉玉樹，改進的Dijkstra算法在GIS路徑規劃中的應用[J].計算機與現代化，2004，(9)：12~14.

[3]張福浩，劉紀平.基于Dijkstra算法的一種最短路徑優化算法[J].遙感信息，2004，(2)：38~41.

[4]嚴蔚敏，吳偉民.數據結構.北京：清華大學出版社.1997.

[5]龔潔輝，白玲.確定地理網絡中心服務的一種算法.測繪學報，1998，27(4).

[6]徐瓊，陳榮清等.基于遺傳算法最短路徑問題的探討.華東地質學院學報，2003，26(2).

[7]吳立新，史文中.地理信息系統原理與算法.北京：科學出版社.2003.

作者簡介：

張弛，男，（1984-），河北邢臺人，2007年畢業于東華理工大學，學士學位，現工作于河北省地礦局第十一地質大隊測繪工程處，助理工程師，研究方向：地理信息系統，3S集成。

邱迎芝，女，（1984-），河北邢臺人，2008年畢業于河北省地質職工大學，本科學歷，現工作于河北省地礦局第十一地質大隊總工辦，助理工程師，研究方向：地質礦產，地理信息系統。