基于WebGIS 的油田應(yīng)急搶險(xiǎn)最短路徑算法研究

任偉建，左方晨，康朝海，王瓊，霍鳳財(cái)

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

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

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

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

1 傳統(tǒng)Dijkstra算法

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

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

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

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

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

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

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

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

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

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

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

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

圖1 Dijkstra算法示意

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

2) 找出已標(biāo)記節(jié)點(diǎn)S={v0}，未標(biāo)號(hào)點(diǎn)的集合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)的終點(diǎn)v1標(biāo)以(1， 0)，表示v0到v1的距離為1，并且在v0到v1的最短路徑中v1前面的1個(gè)點(diǎn)是v0。

3) 此時(shí)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)的終點(diǎn)v2標(biāo)以(3， 1)，表示v0到v2的最短距離為3，并且在v0到v2的最短路徑中v2前面的1個(gè)點(diǎn)是v1。

4) 這時(shí)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)的終點(diǎn)v3標(biāo)以(5， 2)，表示v0到v3的最短距離為5，并且在v0到v3的最短路徑中v3前面的1個(gè)點(diǎn)是v2。

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

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

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

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

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

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

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

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

圖3 電子地圖示意

圖4 拓?fù)浣Y(jié)構(gòu)的道路網(wǎng)絡(luò)示意

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

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

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

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

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

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

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

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

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

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

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

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

表1 同樣起點(diǎn)到終點(diǎn)運(yùn)行時(shí)間對(duì)比

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

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

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

參考文獻(xiàn)：

[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中使用改進(jìn)的Dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算[J].中國(guó)圖象圖形學(xué)報(bào)，2000，5(12)： 1019-1023.

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

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

[6]紀(jì)其進(jìn).一種基于脈沖耦合神經(jīng)網(wǎng)絡(luò)的最短路徑算法[J].小型微型計(jì)算機(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算法的最短時(shí)延路由算法的實(shí)現(xiàn)[J].中國(guó)水運(yùn)，2009，9(02)： 98-99.

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

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

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

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

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

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

[15]羌龍華.基于GIS的油田應(yīng)急指揮系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].自動(dòng)化技術(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]宋士祥，張強(qiáng)，吳明，等.基于GIS和SOA的長(zhǎng)輸管道管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].化工自動(dòng)化及儀表，2012，39(08)： 998-1000，1033.