Dijkstra算法優(yōu)化及其在GIS中的應用

摘 要：本文在詳細介紹經(jīng)典Dijkstra算法和對算法性能深入分析的基礎上，發(fā)現(xiàn)制約經(jīng)典算法的瓶頸是問題的規(guī)模，提出從減少搜索計算頂點數(shù)量入手，對經(jīng)典算法進行改進。詳細分析了算法的設計思想并給出了設計步驟，并通過在ArcGis平臺進行二次開發(fā)驗證了算法的正確性和性能。

關鍵字：Dijkstra算法；最短路徑；GIS

中圖分類號：TP301.6

Dijkstra算法是一種經(jīng)典的求最短路徑的算法。所謂最短路徑問題是指：從帶權(quán)圖的某一頂點出發(fā)，找出一條通往另一頂點的最短路徑。最短路徑問題是GIS應用中研究的一個重要內(nèi)容，在事故搶修、交通指揮、應急管理、GPS導航等應用中都是必要的功能，所以最短路徑分析功能一般會作為基本功能集成到GIS平臺中，如ARCGIS，SuperMap。多數(shù)系統(tǒng)解決最短路徑問題采用Dijkstra算法為理論基礎，它非常適合在帶權(quán)有向圖中求解單源單目的最短路徑問題。

1 經(jīng)典Dijkstra算法

1.1 算法思想

Dijkstra算法是典型最短路算法，用于計算一個頂點到其他所有頂點的最短路徑。其基本思想是，逐步產(chǎn)生最短路徑。首先求出從某一頂點出發(fā)到其他頂點長度最短的一條路徑，然后參照它求出長度次短的路徑，依次類推，按路徑長度的遞增次序，直到計算出該頂點到其他所有頂點的最短路徑。

為了實現(xiàn)該算法，設帶權(quán)圖G=（V，E），V為圖中頂點的集合，E為邊或者弧的集合。設集合S存放已經(jīng)求出的最短路徑的頂點，設集合T為除了S以外的其他頂點，引入輔助數(shù)組dist[]，它的每一個分量dist[i]表示當前找到的從出發(fā)點到頂點i的最短路徑長度。

算法的具體步驟：

（1）初始化：S={V0}；T={V-S}；Dist[j]=Edge[0][j]；j=1，2，…..n-1，n為圖中頂點的個數(shù)；

（2）求出最短路徑長度：dist[k]=min{dist[i]}，i∈V-S；S=S∪{k}；

（3）修改：dist[i]=min{dist[i]，dist[k]+EDedge[k][i]}對于每一個i∈V-S；

（4）判斷：若S=V，則算法結(jié)束，否則轉(zhuǎn)到（2）；

初始時，S中僅含有初始頂點V0，每次從V-S中取出具有最短特殊路長度的頂點，將其添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。

1.2 算法分析

實現(xiàn)經(jīng)典的Dijkstra算法需要兩個并列的for循環(huán)。一個循環(huán)用來實現(xiàn)輔助數(shù)組的初始化工作，時間復雜度為O（n），第二個for循環(huán)是一個二重循環(huán)，實現(xiàn)最短路徑求解的功能，因為圖中所有頂點都要做計算，每個頂點的計算又要對集合S內(nèi)的頂點進行檢測，對集合V-S中的頂點進行修改，所以時間復雜度為O（n2）。算法總的時間復雜度為O（n2），復雜度比較高。

2 Dijkstra算法改進

通過Dijkstra經(jīng)典算法思想可知，計算從u到v的最短路徑時，也計算了u到S中所有頂點的最短路徑，但是，S中的某些頂點可能與最終最短路徑中的頂點無關，該算法在進行最短路徑搜索過程中會涉及到圖中所有的頂點，那么圖中S的大小直接影響著算法的速度。這直接影響了算法的效率，因為由時間復雜度可看出頂點數(shù)量越多所用時間就越長。優(yōu)化該算法勢在必行。

2.1 改進策略

改進的策略用一句話描述就是頂點覆蓋，分段進行。通過前面的分析可知，如果能減少算法中集合S中頂點的個數(shù)，會減少算法的運行時間。在這借用希爾提出希爾排序的思想，把有向圖中的頂點按照某種策略分成若干個小的集合，形成頂點的全覆蓋，這樣每個集合的數(shù)量就比原來少了，但是把他們合起來頂點及關系總數(shù)不變，并且要求不同的集合要有一個連接的關鍵頂點，關鍵點的確定是計算最短路徑的關鍵。

頂點覆蓋劃分的方法可根據(jù)具體的計算應用決定，比如可以按照區(qū)域劃分，按關鍵點劃分，按公路、鐵路線劃分等等。劃分的數(shù)量不宜太多也不宜太少，應根據(jù)實際情況科學分析。劃分數(shù)量和每個劃分中頂點的數(shù)量應事宜，劃分數(shù)量多，重復執(zhí)行的次數(shù)就有可能多；劃分的數(shù)量少對算法的改進程度不高。確定連接不同集合的關鍵點和劃分策略有關，有時也要進行事先的運算，關鍵點應該具有這樣的性質(zhì)，是從一個集合區(qū)域到另一個集合區(qū)域必經(jīng)的頂點或者就是終點。最短路徑的計算結(jié)果是每個小集合劃分的結(jié)果之和得到的。這樣改的好處是，既能減少程序運行時涉及的頂點的數(shù)量，如果采用鄰接矩陣的方式存儲帶權(quán)圖，還能節(jié)省存儲空間。

2.2 算法設計

下面給出改進算法的方法步驟：

（1）根據(jù)劃分策略，確定頂點所屬不同集合Si，i=1，2，3小于等于劃分的個數(shù)，確定存儲表示方法，并建立相應帶全圖；

（2）把所有關鍵點放入關鍵點集合key，并表示關鍵點所連接的區(qū)域信息，并建立拓撲圖；

（3）計算關鍵點集合頂點間的最短路徑，并放入專門的數(shù)組或數(shù)據(jù)表中；

（4）計算任意兩個頂點間的最短路徑，首先判斷頂點所屬范圍，若兩個點均屬于關鍵頂點集合，則直接查找步驟四的計算結(jié)果數(shù)據(jù)表，算法執(zhí)行結(jié)束；若屬于同一個頂點劃分，直接調(diào)用Dijkstra算法，轉(zhuǎn)步驟（5），若屬于不同的集合，轉(zhuǎn)步驟（6）；

（5）在兩頂點所屬劃分Si范圍內(nèi)，直接調(diào)用Dijkstra算法求兩點間的最短距離，算法結(jié)束；

（6）假定兩定點分別屬于劃分Si和Sj，則兩頂?shù)木嚯x等于，u0和v0所屬的集合分別為Ti和Tj，那么最短路徑的計算有三部分組成，先計算起始結(jié)點到與其所在集合Si連接的關鍵點的最短距離，在計算與Sj相連接的關聯(lián)點到終點的最短路徑，再計算兩個關鍵點之間的最短路徑，最后將三部分計算結(jié)果相加，即為兩定點間的最短路徑。

2.3 性能分析

首先該算法是從減少頂點數(shù)量的角度對算法進行優(yōu)化，對經(jīng)典算法本身的執(zhí)行沒有改動，不論是計算關鍵結(jié)點之間的最短路徑，還是計算任意兩個頂點之間的最短路徑，仍然調(diào)用迪杰斯特拉算法，這就保證了算法的可行性。如兩個頂點不屬于同一區(qū)域采用的是分階段計算最短路徑然后相加的方法，減少了計算的復雜性，增強了可理解性和可執(zhí)行性。

其次關于改進算法的時間復雜度，和頂點集合劃分的數(shù)量有關。假設帶權(quán)圖中共有n個頂點，有m個頂點集合劃分，k為關鍵頂點的數(shù)量。時間復雜度分為以下幾種情況：

（1）如果兩頂點均屬于關鍵頂點，則只需要到數(shù)據(jù)表中進行查找，則復雜度取決于關鍵頂點的數(shù)量和查找最短路徑所需要的時間。計算關鍵頂點的復雜度為O（k2），查找路徑可以用優(yōu)化的查找方法；

（2）如果兩頂點屬于同一個集合劃分，復雜度為O（（n/m）2），是沒有改進前的算法復雜度的1/m2。

（3）如果兩頂點，不屬于同一個集合劃分，最短路徑計算是三部分計算之和，三次調(diào)用經(jīng)典算法，復雜度與第二種情況同，但事件應該略多。

從空間復雜度角度，若采用鄰接矩陣的存儲表示方法，經(jīng)典算法需要用n2個存儲空間，改進后只需k*（n/m）2，當然增加了存儲關鍵頂點和其最短路徑的存儲空間，但相比節(jié)省的存儲空間和優(yōu)化的時間復雜度，必要的增加還是值得的。

通過對時間和空間復雜度的分析可以看出改進算法可以極大的減少運算量，降低時間復雜度和空間復雜度。

3 改進算法在GIS中的應用

在ArcGIS平臺中實現(xiàn)改進算法的應用，在Java環(huán)境下利用Arcobject進行二次開發(fā)，采用改進的Dijkstra算法思想編寫函數(shù)，實現(xiàn)最短路徑的搜索。

ArcGIS自帶的網(wǎng)絡分析模塊，具有分析矢量數(shù)據(jù)的功能，只對具有拓撲關系的矢量數(shù)據(jù)進行分析，所以首先在ARCGIS環(huán)境下對地圖進行矢量化，然后進行拓撲分析。本文采用的數(shù)據(jù)是某一地區(qū)的地圖數(shù)據(jù)，文件中一共有3572條地理實體記錄，共有2826個頂點，通過對地圖數(shù)據(jù)的分析，確定了按照地理區(qū)域進行頂點劃分的策略，共分成23個區(qū)域，共找到72個關鍵頂點，每個劃分的頂點根據(jù)地域及關鍵點的鏈接，并不十分平均，但是比起總體的數(shù)據(jù)量，每個集合的規(guī)模都小的多。

利用改進算法進行計算時，按照算法思想采用了兩個頂點在關鍵頂點集合、在兩個不同頂點劃分集合和兩個頂點在同一個頂點集合三組不同的數(shù)據(jù)進行驗證。通過和經(jīng)典的Dijkstra算法運行結(jié)果從正確性和運行時間的對比，證明一方面改進的算法進行最短路徑搜索的結(jié)果和經(jīng)典算法相同的，另一方面比經(jīng)典的算法無論從時間上還是從空間上都有一定的提高。如圖1所示，兩種算法運行時間的對比圖。

圖1 運行時間對比

4 結(jié)束語

本文在分析經(jīng)典Dijkstra算法的基礎上，提出了“頂點覆蓋，分段計算”的思想，進行算法的改進。通過對原帶權(quán)圖中頂點進行覆蓋劃分，減少算法中頂點集合數(shù)目，縮小問題的規(guī)模，并通過分段計算最短路徑以達到降低算法時間復雜度和空間復雜度的目的，經(jīng)在ArcGIS中二次開發(fā)，結(jié)果正確實現(xiàn)了預期設想。

參考文獻：

[1]殷人昆.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）（第二版）[M].北京：清華大學出版社，2007.

[2]王濤春，齊學梅，趙誠.Dijkstra優(yōu)化算法及其在電子導游中的應用[J].安徽師范大學學報（自然科學版），2010（33）：525-529.

[3]陳紅琳.在ArcGis矢量圖中搜尋最短路徑的實現(xiàn)[J].北京測繪，2009（02）：16-18.

[4]王華.基于Dijkstra算法的物流配送最短路徑算法研究[J].計算機與數(shù)字工程，2011（39）：48-50.

[5]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，1997.

作者簡介：馬小雨（1978-），男，河南鄭州人，講師，碩士，研究方向：網(wǎng)絡與安全；余建國（1975-），男，河南林州人，副教授，碩士，研究方向：數(shù)據(jù)庫應用及GIS信息管理。

作者單位：河南工程學院 計算機學院，鄭州 451191；鄭州航空工業(yè)管理學院 計算機科學與應用系，鄭州 450015

基金項目：河南省科技攻關項目（項目編號：132102210172）；鄭州市科技攻關項目（項目編號：20110386）。