基于Dijkstra算法改進的海量數據最優路徑計算方法研究與實現

王兆南

(浙江大學理學院，浙江杭州3100127)

基于Dijkstra算法改進的海量數據最優路徑計算方法研究與實現

王兆南

(浙江大學理學院，浙江杭州3100127)

針對傳統Dijkstra算法在應用中存在的不足，提出一種面向海量數據的基于傳統Dijkstra算法的最優路徑搜索方法，以避免大量無用節點參與計算，嚴重制約計算效率。通過對路網關系制表來表達節點與路段的關系，解決使用相鄰矩陣計算量大的問題。此外，利用監測得到的實時速度進行加權，實現最短時間路徑的計算。

Dijkstra算法;海量數據;最優路徑

一、引 言

面對城市的日益發展和人們生活水平的提高，城市汽車不斷增加，過多的車輛給道路交通帶來了過重的負荷。車道的頻繁整修，節假日的交通管制，都會給道路帶來一定的改變，但是交通部門并不能及時地公布一些車道施工的信息，或者居民不能及時得到已經發布下來的信息，都給居民生活帶來了一些麻煩。通過道路監測與發布系統的建立來及時獲取和發布道路信息將方便人們的出行。本文中的最優路徑分為距離最短路徑和時間最短路徑兩種，其中后者算法是在前者算法基礎上拓展得到的。目前，最短路徑的算法有很多，本系統從最基本的最短路徑的計算方法——Dijkstra算法出發，尋找出一種適合海量數據運算的方法。

二、經典Dijkstra算法的主要思想［1］

Dijkstra算法的基本思路是：假設每個點都有一對標號(dj，pj)。其中，dj是從起源點s到點j的最短路徑的長度;pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：

1)初始化。起源點設置為：① ds=0，ps為空;②所有其他點：di=∞，pi為空;③標記起源點s，記k=s，其他所有點設為未標記的。

2)檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置

式中，lkj是從點k到j的直接連接距離。

3)選取下一個點。從所有未標記的結點集M中，選取dj中最小的一個i：di=min(dj，M)。點i就被選為最短路徑中的一點，并設為已標記的。

4)找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點，設置：i=j*。

5)標記點i。如果所有點已標記，則算法完全推出，否則，記k=i，轉到步驟2)再繼續。

三、本系統最短路徑的實現

可以看出，在按標記法實現Dijkstra算法的過程中，核心步驟就是從未標記的點中選擇一個權值最小的弧段，即上面所述算法的步驟2)～步驟5)。這是一個循環比較的過程，如果不采用任何技巧，未標記點將以無序的形式存放在一個鏈表或數組中，那么要選擇一個權值最小的距離就必須把所有的點都掃描一遍，在大數據量的情況下，這將嚴重制約計算速度。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊進行順序排列，這樣每循環一次只能取到符合條件的點，排除了大量不相連的點，可大大提高算法的執行效率。此外，線路要進行最短路徑的計算，就必須構建網絡的拓撲關系。如果用一個矩陣來表示這個網絡，不但所需空間巨大，而且效率會很低。

本文采用的算法在原有的Dijkstra進行了優化［2］。利用Access數據庫A表達路網的拓撲關系，記錄了節點與路段間的關系和路段的長度，由于是單向路網，為了便于計算，分別以起始節點SNode和終點節點Enode進行排序，并得到兩組數據，一起組成“起終點連接數據.dbm”文件。利用Access數據庫B記錄1～555節點的相鄰連接點的個數和累計的節點個數，累計節點數主要是為了方便算法的實現。本系統的實現過程如下。

首先需要進行數據庫連接，將數據庫中的數據賦到相應的變量中。AA1、BB1、CC1、DD1是以起始節點SNode排序生成的一維數組，其中，AA1對應起始節點SNode;BB1對應終點節點Enode;CC1對應路段長度;DD1對應路段編號。AA2、BB2、CC2、DD2是以ENode排序生成的一維數組，其中，AA2對應ENode;BB2對應SNode;CC2對應路段長度; DD2對應路段編號。IndexA1()和IndexA2()為二維數組，其中，IndexA1()的第1項對應累計數1，第2項對應某一起點與其相鄰的終點的個數;IndexA2()的第1項對應累計數2，第2項對應某一終點與其相連的起點的個數。變量與數據庫字段的相關關系見表1和表2。

表1 數據庫A中獲取的變量

表2 數據庫B中獲取的變量

1.空間最短路徑

空間最短路徑的算法的流程圖如圖1所示。

搜索與ll相連接的點，是先以ll為起點，尋找與ll相連的終點，而以ll為起點得到的終點搜到之后，再以ll為終點，尋找與ll相連的起點的點，算法過程與上面一樣。經過兩個循環便將與ll相連的點全部找出，再從中找出長度最短的點，賦給Min-Point。如此循環完成空間上最短路徑的搜索。

2.時間最短路徑

時間最短路徑的算法和空間最短路徑算法的流程基本相同，其算法流程圖如圖2所示。

圖1 空間最短路徑算法流程圖

圖2 時間最短路徑算法流程

主要代碼思想如下：首先進行初始化，初始化過程與空間最短路徑的過程一樣，開始搜索與ll相連接的點，先以ll為起點，尋找與ll相連的終點，主要代碼和空間最短路徑的過程類似。在過程中要對路況監督時得到的速度進行匹配，以解決兩個模塊使用的表順序不一致的問題。速度求得之后，便可進行時間的計算。求出的是走到此點所花的累積時間S1，再以ll為起點搜到終點之后，再以ll為終點，尋找與ll相連的起點的點，算法過程與上面一樣。經過兩個循環便將與ll相連的點全部找出，再從中指出時間最短的點，賦給MinPoint。

如此循環完成時間上的最短路徑的搜索。

四、最短路徑功能實現

最短路徑的搜索及結果在地圖上顯示的全過程如圖3所示。

圖3 路徑選擇實現過程流程圖

主要實現的功能有：在組合框中利用模糊匹配進行選擇路口的選擇;在列表框中顯示選擇的要經過的路口的信息;對列表框中的信息進行刪除、上移、下移基本操作;實現空間時間最短路徑的計算;在地圖上實現最短路徑的高亮顯示。

1.最短路徑計算

對于空間最短路徑的計算，依照ListView中所選擇的點的順序多次調用ShortPath()過程實現，時間最短路徑的計算調用TShortPath()過程實現。

2.結果的地圖顯示

最短路徑計算結束后，經過的路段的編號以字符串的形式儲存在SumPath的變量中，利用Split將SumPath中的路段號提取出來放入一個數組。給搜索的路段進行著色，將最短路徑進行高亮顯示，渲染后的效果如圖4所示。若是空間最短，在最短路徑的窗口的查詢結果中展現整段路程的最短長度;若是時間最短，記錄下所花的最短的時間。

圖4 地圖高亮顯示的效果

如要從四平路國泰路出發經過控江路軍工路，最后抵達軍工路殷行路，需要知道空間上的最短路徑。打開主界面的路徑選擇菜單，在選擇最短路徑類型欄中選擇空間最短，按照順序將3個路口的名稱輸入，單擊計算，便出現如圖4所示的結果。系統會在最短路徑頁面的最下方查詢結果的文本框中顯示“從起點四平路國泰路到終點軍工路殷行路空間的最短路程為8 797.934 m”。同時，在主界面的地圖上還會用橙色標出最短路徑經過的路線。

五、結束語

本文通過對路網關系制表來表達節點與路段的關系，解決了使用相鄰矩陣計算量大的問題。此外，利用監測得到的實時速度進行了加權，實現了最短時間路徑的計算，并對最短路徑進行高亮顯示，使路線一目了然。但是，本方法實現的過程還有可以改進的地方，如最短路徑的模型相對簡單，可以加入車道信息和轉向信息等。

［1］ 樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實現［J］.武漢測繪科技大學學報，1999，24(3)：209-211.

［2］ 孫慶珍，李宏偉.GIS中最短路徑算法的研究以及在VB中的代碼［J］.電腦編程與維護，2005(8)：30-32.

Mass Data Optimal Path Searching Using an Improved Dijkstra Algorithm

WANG Zhaonan

0494-0911(2012)09-0032-03

P208

B

2012-07-16

王兆南(1990—)，男，山東肥城人，主要研究方向為地理信息系統應用與開發。