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

關(guān)鍵字：Dijkstra算法；最短路徑；GIS

中圖分類(lèi)號(hào)：TP301.6

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

1 經(jīng)典Dijkstra算法

1.1 算法思想

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

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

算法的具體步驟：

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

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

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

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

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

1.2 算法分析

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

2 Dijkstra算法改進(jìn)

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

2.1 改進(jìn)策略

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

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

2.2 算法設(shè)計(jì)

下面給出改進(jìn)算法的方法步驟：

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

（2）把所有關(guān)鍵點(diǎn)放入關(guān)鍵點(diǎn)集合key，并表示關(guān)鍵點(diǎn)所連接的區(qū)域信息，并建立拓?fù)鋱D；

（3）計(jì)算關(guān)鍵點(diǎn)集合頂點(diǎn)間的最短路徑，并放入專(zhuān)門(mén)的數(shù)組或數(shù)據(jù)表中；

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

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

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

2.3 性能分析

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

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

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

（2）如果兩頂點(diǎn)屬于同一個(gè)集合劃分，復(fù)雜度為O（（n/m）2），是沒(méi)有改進(jìn)前的算法復(fù)雜度的1/m2。

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

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

通過(guò)對(duì)時(shí)間和空間復(fù)雜度的分析可以看出改進(jìn)算法可以極大的減少運(yùn)算量，降低時(shí)間復(fù)雜度和空間復(fù)雜度。

3 改進(jìn)算法在GIS中的應(yīng)用

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

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

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

圖1 運(yùn)行時(shí)間對(duì)比

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

基金項(xiàng)目：河南省科技攻關(guān)項(xiàng)目（項(xiàng)目編號(hào)：132102210172）；鄭州市科技攻關(guān)項(xiàng)目（項(xiàng)目編號(hào)：20110386）。