任偉建，左方晨，康朝海，王瓊，霍鳳財

(東北石油大學(xué) 電氣信息工程學(xué)院，黑龍江 大慶 163318)

網(wǎng)絡(luò)分析作為網(wǎng)絡(luò)地理信息系統(tǒng)(WebGIS)最主要的功能之一，是地理信息系統(tǒng)(GIS)的重要組成部分，在電子導(dǎo)航、交通旅游、城市規(guī)劃、電力、通信等各種管網(wǎng)及管線的布局設(shè)計中發(fā)揮著重要的作用。而最短路徑是WebGIS網(wǎng)絡(luò)分析最基本、最關(guān)鍵的問題，在交通網(wǎng)絡(luò)結(jié)構(gòu)的分析、交通運輸線路的選擇、通信線路的建造與維護、運輸貨流的最小成本分析、城市公共交通網(wǎng)絡(luò)的規(guī)劃等方面，都有直接應(yīng)用的價值[1]。

隨著人們對安全、環(huán)境的重視以及油田突發(fā)事件的增多，油田應(yīng)急系統(tǒng)的研究和應(yīng)用越來越廣泛。油田應(yīng)急救援過程應(yīng)能夠及時、有效地將應(yīng)急資源運送到事故現(xiàn)場，這就涉及最短路徑問題。但在應(yīng)急搶險的過程中，最短路徑需要綜合考慮路徑的屬性、資源運送的時效性、安全性、經(jīng)濟性等因素。為此，在搶險過程中，采用合適的最短路徑搜索算法，盡量減少計算機的運算時間，是研究最短路徑的一個重要方向[2]。

最短路徑算法主要包括圖論基本方法[3]、啟發(fā)式搜索方法[4]、動態(tài)規(guī)劃方法[5]、神經(jīng)網(wǎng)絡(luò)方法[6]等。啟發(fā)式搜索方法多采用A*算法，但由于其執(zhí)行時間通常為指數(shù)級，故一般較少采用；動態(tài)規(guī)劃方法是一種解決多階段決策問題的有效方法，但其動態(tài)決策過程中需要存儲大量的階段狀態(tài)信息，故該算法目前主要適于普通小型試驗級網(wǎng)絡(luò)的最短路徑處理；神經(jīng)網(wǎng)絡(luò)方法是一種新興的算法，但由于其不成熟性，計算效率也較低，故較少采用；在實際過程中使用最多的是圖論基本方法，其中較為常用的就是迪杰斯特拉(Dijkstra)算法。由于Dijkstra算法能適應(yīng)網(wǎng)絡(luò)拓撲的變化，性能穩(wěn)定，因而在計算機網(wǎng)絡(luò)拓撲路徑選擇以及WebGIS中得到了廣泛的應(yīng)用。目前在國內(nèi)外有許多學(xué)者對Dijkstra算法進行了許多卓有成效的研究、改進和優(yōu)化[7-9]，其中有兩種改進后算法的測試效果較好，分別是： DKA(the Dijkstra’s algorithm implemented with approximate buckets)和DKD(the Dijkstra’s algorithm implemented with double buckets)，適合對2個節(jié)點間的最短路徑問題進行求解。當(dāng)面對大型的網(wǎng)絡(luò)、對時效要求很高的問題時，這些算法的搜索效率會嚴重地降低，也不能滿足問題解決的需要。筆者針對WebGIS網(wǎng)絡(luò)分析中的最短路徑問題，在Dijkstra算法的基礎(chǔ)上，對其數(shù)據(jù)結(jié)構(gòu)和計算方法作了一系列的改進，優(yōu)化了系統(tǒng)的性能并采用面向?qū)ο蟮姆绞綄崿F(xiàn)了該算法，算法效率得到了明顯提高。

1 傳統(tǒng)Dijkstra算法

Dijkstra算法是Dijkstra E W于1959年提出的一種按路徑長度遞增的次序產(chǎn)生最短路徑的算法，被認為是解決單源點間最短路徑問題比較經(jīng)典而且有效的算法。其基本思想是生成1棵以固定起點為根的最短路徑生成樹[10]。根到樹中每個節(jié)點的路徑即為根到該點的最短路徑，因為傳統(tǒng)Dijkstra算法所求問題的網(wǎng)絡(luò)中不存在負權(quán)，所以這棵最短路徑生成樹在生成過程中，將對各節(jié)點按其距固定起點的遠近以及點間的鄰接關(guān)系來逐個加入到樹中，先近后遠。

Dijkstra的表述通常有兩種方式： 用永久和臨時標(biāo)號方式(Dijkstra算法也被稱為標(biāo)號作業(yè)法，通過不斷地迭代產(chǎn)生出所有的永久標(biāo)號)；用OPEN，CLOSE表方式。文中采用的是永久和臨時標(biāo)號方式，算法的過程如下[11，16]：

設(shè)G=(V，E)是1個帶權(quán)值有向圖(這里權(quán)值可以是長度，也可以是時間、費用等)，把圖中節(jié)點集合V分成2組： 第1組為已求出最短路徑的節(jié)點集合(用S表示，初始時S中只有1個起始節(jié)點，以后每求得1條最短路徑，就將其加入到節(jié)點集合S中，直到全部節(jié)點都加入到S中，算法結(jié)束)；第2組為剩余的還沒確定的最短路徑節(jié)點的集合(用U來表示)，依據(jù)最短路徑長度的遞增順序把第2組中的節(jié)點依次地加入到集合S中。在加入的過程中，總保持從起始節(jié)點v到S中各個節(jié)點的最短路徑的長度不大于從起始節(jié)點v到U中任何節(jié)點的最短路徑的長度。此外，每一個節(jié)點都對應(yīng)著一個長度，S中節(jié)點的長度就是從v到此節(jié)點的最短路徑的距離；U中節(jié)點的長度，是從v到此節(jié)點只包括S中的節(jié)點為中間節(jié)點的當(dāng)前最短路徑長度。

1.1 Dijkstra算法的標(biāo)號

對圖中的某點vj賦予2個標(biāo)號(l，k)，第1個標(biāo)號l表示從起點v0到vj最短路徑的長度；第2個標(biāo)號k表示在v0到vj的最短路徑上的vj前面1個鄰點的下標(biāo)，從而找到起點v0到終點的最短路徑及v0到終點vt的距離。算法的基本步驟如下：

1) 給起點v0以標(biāo)號(0，k)，表示v0到v0的距離為0，v0為起點。

2) 找出已標(biāo)號的點的集合S，未標(biāo)號的點的集合U以及弧的集合{(vm，vn)|vm∈S，vn∈U}(m，n∈j)，這里弧的集合是指所有從已標(biāo)號的點到未標(biāo)號的點的弧的集合，其中vm表示已經(jīng)標(biāo)號的節(jié)點，vn表示與vm相鄰未標(biāo)號的節(jié)點。

3) 如果{(vm，vn)|vm∈S，vn∈U}是空集，則計算結(jié)束。如果終點vt已標(biāo)號(l，k)，則v0到終點vt的距離為l，而從v0到vt的最短路徑，則可以從vt反向追蹤到起點v0而得到。如果上述集合不是空集則轉(zhuǎn)下一步。

4) 對于上述集合中的每一條弧，計算sm n=l+cm n(cm n表示已標(biāo)號節(jié)點vm到未標(biāo)號節(jié)點vn的距離)，在所有sm n中，找到其值為最小的弧。則給此段弧的終點v標(biāo)以雙標(biāo)號(sm n，k)，返回步驟2)，以此類推。

若在步驟4)中，使得sm n值為最小的弧有多條，則這些弧的終點既可以任選1個標(biāo)定，也可以都予以標(biāo)定，若這些弧中有些弧的終點為同1點，則此點應(yīng)有多個雙標(biāo)號，以便最后可找到多條最短路徑。

1.2 Dijkstra算法的應(yīng)用

例如求圖1中v0到v3的最短路徑：

圖1 Dijkstra算法示意

1) 給起點v0以標(biāo)號(0，k)，表示v0到v0的距離為0，v0為起點。

2) 找出已標(biāo)記節(jié)點S={v0}，未標(biāo)號點的集合U={v1，v2，v3}以及弧的集合{(vm，vn)|vm∈S，vn∈U}={(v0，v1)，(v0，v2)}。

s01=l0+c01=0+1=1

s02=l0+c02=0+4=4

Min(s01，s02)=s01=1

這樣給弧(v0，v1)的終點v1標(biāo)以(1， 0)，表示v0到v1的距離為1，并且在v0到v1的最短路徑中v1前面的1個點是v0。

3) 此時S={v0，v1}，U={v2，v3}，弧集合{(vm，vn)|vm∈S，vn∈U}={(v0，v2)， (v1，v2)， (v1，v3)}。

s02=l0+c02=0+4=4

s12=l1+c12=1+2=3

s13=l1+c13=1+5=6

Min(s02，s12，s13)=s12=3

這樣給弧(v1，v2)的終點v2標(biāo)以(3， 1)，表示v0到v2的最短距離為3，并且在v0到v2的最短路徑中v2前面的1個點是v1。

4) 這時S={v0，v1，v2}，U={v3}，弧集合{(vm，vn)|vm∈S，vn∈U}={(v1，v3)， (v2，v3)}。

s13=l1+c13=1+5=6

s23=l2+c23=3+2=5

Min(s13，s23)=s23=5

這樣給弧(v2，v3)的終點v3標(biāo)以(5， 2)，表示v0到v3的最短距離為5，并且在v0到v3的最短路徑中v3前面的1個點是v2。

5) 這時S={v0，v1，v2，v3}，弧集合{(vm，vn)|vm∈S，vn∈U}=φ，計算完成，如圖2所示。

圖2 Dijkstra算法標(biāo)號示意

根據(jù)v3的標(biāo)號可得v0到v3的距離是5，最短路徑為v0—v1—v2—v3。

按標(biāo)記法實現(xiàn)Dijkstra算法的過程中，核心步驟就是從未標(biāo)記的點中選擇1個權(quán)值最小的弧段，即1.1節(jié)所述算法的2)～4)。這是一個循環(huán)比較的過程，如果不采用任何技巧，未標(biāo)記點將以無序的形式存放在1個鏈表或數(shù)組中。那么要選擇1個權(quán)值最小的弧段就必須把所有的點都掃描一遍，在大數(shù)據(jù)量的情況下，這無疑是制約計算速度的瓶頸。

2 Dijkstra算法的優(yōu)化

Dijkstra算法是目前大多數(shù)系統(tǒng)解決最短路徑問題的基礎(chǔ)。Dijkstra算法的優(yōu)點是程序設(shè)計簡單、通用性強，但不是專門針對特定2個點的，而在WebGIS中，往往是尋找2個特定點間的最短路徑，此時Dijkstra算法的效率會降低，而且Dijkstra算法采用的鄰接數(shù)據(jù)矩陣結(jié)構(gòu)，占用空間十分巨大，嚴重浪費了計算機的資源，影響計算速度，不適合WebGIS節(jié)點量巨大的實際情況。因此在WebGIS應(yīng)用中，對Dijkstra算法的改進是十分必要的。筆者從WebGIS的存儲空間以及算法的本身出發(fā)對Dijkstra算法提出了優(yōu)化和改進，使之更適合WebGIS中針對固定2個點間最短路徑的實際情況。

2.1 WebGIS存儲空間的優(yōu)化

最短路徑優(yōu)化研究應(yīng)盡量減少算法占用的存儲空間。WebGIS中的數(shù)據(jù)(如道路、管網(wǎng)、線路等)要進行最短路徑的計算，就必須將其按節(jié)點和邊的關(guān)系抽象為圖的結(jié)構(gòu)，這在WebGIS中稱為構(gòu)建網(wǎng)絡(luò)的拓撲關(guān)系(這里的拓撲關(guān)系僅記錄了線與節(jié)點的關(guān)系而無線與面的關(guān)系，是不完備的拓撲關(guān)系)[12]。對于圖3所示的電子地圖，要計算圖中2個點間的最短路徑，需將圖3中道路抽象為具有拓撲結(jié)構(gòu)的道路網(wǎng)絡(luò)，如圖4所示。

圖3 電子地圖示意

圖4 拓撲結(jié)構(gòu)的道路網(wǎng)絡(luò)示意

具有拓撲結(jié)構(gòu)的道路網(wǎng)絡(luò)由節(jié)點、邊及相應(yīng)的拓撲關(guān)系構(gòu)成。其中節(jié)點是道路的交叉點、端點，邊是2個點間的一段道路。在網(wǎng)絡(luò)分析過程中，實際只需關(guān)心網(wǎng)絡(luò)邊的信息，如邊的權(quán)值、起點、終點，就可采用只存儲邊的網(wǎng)絡(luò)拓撲信息，不存儲實際節(jié)點的拓撲信息，減少空間分析時所要檢索的數(shù)據(jù)量。

另外對節(jié)點和弧段等數(shù)據(jù)采取動態(tài)管理的策略，也會減少算法占用的存儲空間。所謂動態(tài)管理，是指算法的開始，并不是創(chuàng)建整個網(wǎng)絡(luò)中的節(jié)點和弧段的數(shù)據(jù)結(jié)構(gòu)，而是根據(jù)算法運行的需要，動態(tài)地生成、擴展以及刪除相應(yīng)的節(jié)點。對數(shù)據(jù)實行動態(tài)管理的策略，能夠最大限度地發(fā)揮存儲空間的利用效率，避免無效數(shù)據(jù)占用大量的存儲空間。

2.2 直線法優(yōu)化Dijkstra算法

直線法優(yōu)化Dijkstra算法是指通過減小算法中的搜索范圍，以盡快達到目標(biāo)節(jié)點。其核心思想： 在把研究的網(wǎng)絡(luò)看成平面網(wǎng)絡(luò)的前提下，將臨時標(biāo)記節(jié)點到源點的最短路徑與該臨時標(biāo)記節(jié)點到目標(biāo)節(jié)點的直線距離之和，作為此臨時標(biāo)記節(jié)點的一個屬性值，即選取此屬性值最小的臨時節(jié)點作為永久標(biāo)記節(jié)點，這種優(yōu)化算法稱為直線優(yōu)化算法。此方法使得Dijkstra算法的搜索方向智能地趨向目標(biāo)節(jié)點，減少了算法中遍歷的節(jié)點個數(shù)，從而提高了搜索速度。

受直線優(yōu)化算法的啟發(fā)，結(jié)合WebGIS的數(shù)據(jù)組織方法可以采取一種優(yōu)先搜索的方法。 從幾何的知識可知2個點之間直線距離最短，在錯綜復(fù)雜的道路網(wǎng)上，任選2個點，其最短路徑可設(shè)為1條從起點到終點的直線，該直線作為1條道路存在的可能性很小，但該線代表著1條路線的趨勢，順著這個方向的某條路徑是起點到終點的最短路徑的可能性極大。

如圖5所示，求A點到E點的最短路徑，可以在AE間虛擬一條連接2個點的直線，然后比較A點到鄰接點間的路段與此虛擬直線的夾角，找出夾角最小的1條AB優(yōu)先處理；接下來以B點代替A，以B為起點，以同樣的方法找出與BE夾角最小的路段BF優(yōu)先處理；接著以F點代替B點，以F點為起點，以同樣的方法找出與FE夾角最小的路段FI優(yōu)先處理。以此類推，最終找出1條最短路徑。

由上可知，改進后的算法是在起點和終點間建立樹狀網(wǎng)絡(luò)拓撲的過程，同時也是路徑搜索的過程，只是在搜索過程中采用了一定的技巧，將未搜索的路徑以有方向、有目的的形式進行，從而降低原算法中搜索那些與終點背道而馳的路徑而導(dǎo)致算法效率低下的問題，大幅提高了計算機的運行速度。

圖5 直線優(yōu)化算法路徑示意

3 改進后的Dijkstra算法在油田應(yīng)急搶險系統(tǒng)中的應(yīng)用

油田應(yīng)急搶險系統(tǒng)是集GIS、數(shù)據(jù)庫、多媒體、語音技術(shù)及現(xiàn)代通信技術(shù)為一體的多功能輔助決策系統(tǒng)，是WebGIS空間分析的一個重要方向[13-15]。系統(tǒng)主要功能： 利用該系統(tǒng)的空間查詢技術(shù)確定事故發(fā)生地點，快速顯示采油廠的電子地圖和地理信息，在電子地圖上顯示各主要功能單位(如119，110，120和物資儲備庫)到事故發(fā)生地點的最佳行駛路線。

該系統(tǒng)利用ArcGIS Server 9.3 組件，在Visual C#下實現(xiàn)最佳路徑的查詢功能，針對油田道路網(wǎng)絡(luò)的具體情況，完成了改進后的Dijkstra算法在油田應(yīng)急搶險系統(tǒng)中的應(yīng)用，實現(xiàn)了單目標(biāo)點—多源點最佳路徑查詢工作。該道路網(wǎng)中共有258個節(jié)點，221段弧，在主頻為3.40 GHz、內(nèi)存2G的計算機中，計算5條總長度為15 667 m路徑，耗時約1.375 s。

用不同的道路數(shù)據(jù)，在同一臺電腦上，筆者又多次模擬求解同樣起點到終點的距離，表1顯示了該算法和Dijkstra算法的運行時間結(jié)果對照。

表1 同樣起點到終點運行時間對比

從表1可以看出，當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)較少時，兩種算法的運算時間相差不多，效率差異不明顯；但隨著網(wǎng)絡(luò)中節(jié)點數(shù)目的增多，Dijkstra算法需要遍歷圖中所有的節(jié)點，效率會降低，而該算法按照一定的搜索方向，減少了搜索節(jié)點的個數(shù)，提高了搜索速度，完全滿足了油田應(yīng)急搶險系統(tǒng)所要求的最佳時間(1～2 s)。

4 結(jié)束語

文中詳細地介紹了Dijkstra算法的基本原理，并且結(jié)合WebGIS的實際情況，對原有的算法提出了優(yōu)化方法。既節(jié)省了存儲空間，又提高了運行效率，使得Dijkstra算法真正地應(yīng)用到油田應(yīng)急搶險系統(tǒng)中。然而，目前道路網(wǎng)越來越復(fù)雜，也越來越龐大，在應(yīng)用過程中必須要考慮眾多因素，如道路擁擠程度、道路等級、交叉口的延誤時間、交通管制信息等，因而尋找考慮多種因素的最優(yōu)應(yīng)急搶險路徑，將是需要進一步研究的問題。

參考文獻：

[1]PALLOTLINO S. Shortest Path Methods： Complexity， Interrelation and New Propositions. Networks[J]. 1984， 14(02)： 257-267.

[2]王一軍，羅大庸，張航.城市應(yīng)急最優(yōu)路徑算法[J].系統(tǒng)工程，2008，26(07)： 86-91.

[3]唐文武，施曉東，朱大奎.GIS中使用改進的Dijkstra算法實現(xiàn)最短路徑的計算[J].中國圖象圖形學(xué)報，2000，5(12)： 1019-1023.

[4]魏唯，歐陽丹彤，呂帥，等.一種多目標(biāo)增量啟發(fā)式搜索算法[J].吉林大學(xué)學(xué)報，2009，47(04)： 752-758.

[5]趙慧娟，湯兵勇，張云.基于動態(tài)規(guī)劃法的物流配送路徑的隨機選擇[J].計算機應(yīng)用及軟件，2013，4(30)： 110-112.

[6]紀其進.一種基于脈沖耦合神經(jīng)網(wǎng)絡(luò)的最短路徑算法[J].小型微型計算機系統(tǒng)，2005，26(05)： 826-829.

[7]ZHAN F B. Three Fastest Shortest Path Algorithms on Real Road Networks[J]. Journal of Geographic Information and Decision Analysis， 1997，1(01)： 69-82.

[8]熊碧霞，楊春蘭.基于Dijkstra算法的最短時延路由算法的實現(xiàn)[J].中國水運，2009，9(02)： 98-99.

[9]陳靈敏.最短路徑算法在高速公路聯(lián)網(wǎng)收費中的研究及應(yīng)用[M].貴州大學(xué)學(xué)報(自然科學(xué)版)，2009，26(01)： 47-50.

[10]GILLES B， PAUL B. Fundamentals of Algorithmics(算法基礎(chǔ))[M].邱仲潘，柯渝，徐峰，等，譯.北京： 清華大學(xué)出版社，2005： 154-157.

[11]胡洪林.求最短路徑的Dijkstra算法原理分析[J].計算機科學(xué)，2008，34(07)： 60-74.

[12]王陵，段江濤，王保保.GIS中最短路徑的算法研究與仿真[J].計算機仿真，2005，22(01)： 117-120.

[13]姜鳳輝，李樹軍，姜鳳嬌.基于GIS的Dijkstra改進算法及其在交通導(dǎo)航系統(tǒng)中的應(yīng)用[J].測繪與空間地理信息，2011，34(04)： 129-131.

[14]高曉榮，徐英卓.油田事故應(yīng)急救援可視化決策支持系統(tǒng)[J].計算機工程，2010，36(15)： 236-239.

[15]羌龍華.基于GIS的油田應(yīng)急指揮系統(tǒng)的設(shè)計與實現(xiàn)[J].自動化技術(shù)與應(yīng)用，2011，30(07)： 38-41.

[16]SCHULZ F，WAGNER D，WEIHE K. Dijkstra’s Algorithm Online： An Empirical Case Study From Public Railroad Transport[J].Journal of Experimental Algorithmics，2000(05)： 110-123.

[17]宋士祥，張強，吳明，等.基于GIS和SOA的長輸管道管理系統(tǒng)的設(shè)計與實現(xiàn)[J].化工自動化及儀表，2012，39(08)： 998-1000，1033.