Dijkstra算法在GIS車輛誘導(dǎo)系統(tǒng)的優(yōu)化實現(xiàn)

殷招偉 戴文博 錢俊彥

（桂林電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004）

Dijkstra算法在GIS車輛誘導(dǎo)系統(tǒng)的優(yōu)化實現(xiàn)

殷招偉 戴文博 錢俊彥

（桂林電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004）

為了滿足人們?nèi)找嬖鲩L的出行需求，跨學(xué)科的智能交通系統(tǒng)應(yīng)運而生。最短路徑分析是GIS車輛誘導(dǎo)系統(tǒng)應(yīng)用的關(guān)鍵問題，Dijkstra算法是解決該問題的常用算法。文章結(jié)合二樹Dijkstra算法的思想和現(xiàn)代多核多線程的技術(shù)，對Dijkstra算法進(jìn)行了優(yōu)化與改進(jìn)，并對該算法在車輛誘導(dǎo)系統(tǒng)中的應(yīng)用進(jìn)行了探討。該系統(tǒng)以桂林市為例模擬了最短路徑搜過程，證明該算法的高效性和實用性。

最短路徑；Dijkstra算法；車輛誘導(dǎo)系統(tǒng)

車輛誘導(dǎo)系統(tǒng)作為智能交通系統(tǒng)的子系統(tǒng)，在交通管理上發(fā)揮著重要作用。地理信息系統(tǒng) GIS(Geographical Information System)以其強(qiáng)大功能應(yīng)用在電子地圖應(yīng)用在車輛誘導(dǎo)系統(tǒng)中[1]，其核心問題是求解最短路徑問題。最短路徑問題是指在一定的評判準(zhǔn)則下，尋找源點到目標(biāo)節(jié)點之間的最優(yōu)路徑[1]。

用于解決最短路徑問題的算法被稱作“最短路徑算法”[2]，包括傳統(tǒng)Dijkstra算法、A*算法和各種限制搜索區(qū)域算法。最常用且最典型的為Dijkstra算法，由于該算法是一種窮盡遍歷算法，必定會找到最短路徑，但對于節(jié)點數(shù)目巨大的交通網(wǎng)絡(luò)，其搜索效率很低。本文對該算法進(jìn)行優(yōu)化和改進(jìn)，利用該優(yōu)化算法可以快速找到最優(yōu)路徑。最終將其應(yīng)用于車輛誘導(dǎo)系統(tǒng)中，為人們出行提供便利，并證明該算法的實用性。

1 Dijkstra算法

荷蘭計算機(jī)學(xué)科教授迪杰斯特（E.W.Dijkstra）于1959年提出了Dijkstra算法。該算法被公認(rèn)為是最經(jīng)典的算法之一，也是解決最短路徑問題的基礎(chǔ)算法。它可以描述為從某點到網(wǎng)絡(luò)中其余定點的路徑長度依次遞增的最短路經(jīng)樹，換言之Dijkstra算法是用于計算網(wǎng)絡(luò)中起始節(jié)點s到其他所有可達(dá)節(jié)點的最短路徑樹。在實際求解最短路徑過程中，一旦發(fā)現(xiàn)路徑樹中已經(jīng)存在目標(biāo)節(jié)點t，則終止算法。其中，最短路徑起始節(jié)點s到目標(biāo)節(jié)點t的路徑就是最短路徑。Dijkstra算法將網(wǎng)絡(luò)中節(jié)點分為三類：未標(biāo)記節(jié)點、候選節(jié)點和永久節(jié)點。算法初始化時把所有節(jié)點初始化為未標(biāo)記節(jié)點，找到與起始節(jié)點有最短路徑的節(jié)點稱作是永久節(jié)點，在路搜索過程中與永久節(jié)點相連的節(jié)點標(biāo)記為候選節(jié)點。算法可以描述為在循環(huán)搜索，在候選節(jié)點集合中查找出距離源節(jié)點 s最近的節(jié)點，同時將該節(jié)點標(biāo)記為永久節(jié)點，直至把目標(biāo)節(jié)點或者所有節(jié)點標(biāo)成永久節(jié)點為止。其算法描述如下：

上述算法過程描述中，有向圖G可以用[N,A]來表示，其中N為所有節(jié)點集合，A表示所有邊的集合。邊(i,j)∈A的權(quán)值用lij表示。假設(shè)存在最短路徑節(jié)點s到節(jié)點t，并且所有邊(i,j)滿足 lij≥0。FS(u)表示節(jié)點 u所有后繼節(jié)點(u,j)∈A的集合，u∈N；BS(v)表示節(jié)點v所有前驅(qū)節(jié)點的集合，(i,v)∈A，v∈N。標(biāo)簽集合du用來表示路徑樹T中根節(jié)點到各個節(jié)點路徑長度；pu表示路徑樹 T中的上級節(jié)點；Q表示候選節(jié)點集合。

2 Dijkstra算法優(yōu)化與改進(jìn)

Dijkstra算法是一種窮盡遍歷算法，其核心思想是遍歷完所有的節(jié)點，找到根節(jié)點到目標(biāo)節(jié)點之間所有的可達(dá)路徑并從中選出最短路徑。因此，在搜索過程中即使一開始找到最短路徑也要繼續(xù)遍歷完其他所有節(jié)點，結(jié)果會消耗不必要的內(nèi)存資源，降低搜索效率。因此在實際當(dāng)中，需要優(yōu)化搜索方方式，其主要分為兩種：一是加快搜索速度；另外就是減少搜索節(jié)點數(shù)目。本文從減少搜索節(jié)點數(shù)目這個方面優(yōu)化Dijkstra算法。

2.1 二樹Dijkstra算法

二樹Dijkstra算法最早由Dantzig在文獻(xiàn)[3]中提出，但是他并未給出算法結(jié)束的條件。Pohl在文獻(xiàn)[4]補(bǔ)充該算法為雙向搜索算法，形成了較為完善的二樹Dijkstra算法。

二樹Dijkstra算法基本思想就是構(gòu)造兩棵分別以起點為根和以終點為根最短路徑搜索樹，它們擁有相同的節(jié)點。然后分別以這兩棵路徑搜索樹沿著相反的方向開始搜索，同時在當(dāng)前的上級節(jié)點中保存的是前驅(qū)節(jié)點而不是后繼節(jié)點。其中，兩棵樹是以交替的形式增長，故該算法又稱串行二樹Dijkstra算法，當(dāng)兩棵樹中出現(xiàn)相同節(jié)點時結(jié)束算法。這個相同節(jié)點稱作公共節(jié)點。但需要注意的是，兩棵樹中出現(xiàn)公共節(jié)點并不是得到最短路徑的必要條件，即找到的公共節(jié)點不一定在最短路徑上。該算法所需的存儲空間是Dijkstra算法的兩倍，算法流程如下：

2.2 二樹Dijkstra算法的改進(jìn)

二樹Dijkstra算法中，我們可以看到兩棵路徑搜索樹是相互獨立的，唯一關(guān)聯(lián)的是需要檢測兩棵樹中是否存在公共節(jié)點。在多核多線程技術(shù)中，關(guān)聯(lián)并不會造成任何的干擾[5]。因此，通過為兩棵路徑樹創(chuàng)建兩個線程來擴(kuò)張節(jié)點，就實現(xiàn)了并行的二樹Dijkstra算法。當(dāng)其中一個線程檢測到公共節(jié)點時，則通知另一個線程同時結(jié)束算法，算法流程如下圖所示。

相比串行二樹Dijkstra算法，并行二樹Dijkstra算法在搜索過程中是從兩個方向同時進(jìn)行搜索，因此其搜索效率是串行二樹Dijkstra算法的兩倍。但在實際編碼實現(xiàn)過程要考慮到線程之間的同步與互斥，即對臨界資源的加鎖與解鎖。因此實際的并行二樹 Dijkstra算法的效率達(dá)不到串行二樹Dijkstra算法的兩倍，但其實際搜索效率仍然高于串行二樹Dijkstra算法。其搜索范示意圖如圖1所示。

圖1 算法搜索范圍示意圖

2.3 測試結(jié)果與分析

將本文中提出的上述三種算法應(yīng)用到路網(wǎng)分析中，因為路網(wǎng)中節(jié)點數(shù)目較多，故其數(shù)據(jù)結(jié)構(gòu)采用鄰接表存儲。測試數(shù)據(jù)來源DIMACS網(wǎng)站提供的美國道路網(wǎng)信息，測試結(jié)果如表2所示，其中的T表示消耗時間，單位為妙，W表示搜索路徑的權(quán)值。

表2 算法結(jié)果統(tǒng)計表

從表中可以得到，在搜索過程中消耗的時間關(guān)系是：Dijkstra算法＞二樹Dijkstra算法＞并行二樹Dijkstra算法。在準(zhǔn)確性方面，Dijkstra算法求解出來的一定是最短路徑，盡管二樹Dijkstra算法和并行二樹Dijkstra算法的不能保證其結(jié)果一定是最短路徑，但是非常接近Dijkstra算法的結(jié)果。在大量實驗的基礎(chǔ)上，并行二樹Dijkstra算法的算法結(jié)果準(zhǔn)確率在90%以上，基本滿足人們的出行要求。

3 并行二樹 Dijkstra算法在 VRGS中的應(yīng)用

因為城市路網(wǎng)中節(jié)點數(shù)目巨大，故在改進(jìn)算法中采用鄰接表作為存儲結(jié)構(gòu)，在保證道路完整性的前提下大幅減低了空間復(fù)雜度[6]。最終將本文提出的改進(jìn)算法—二樹 Dijkstra算法應(yīng)用到車輛誘導(dǎo)系統(tǒng)中。

3.1 算法設(shè)計實現(xiàn)

建立道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。定義一個Node類，用來表示點要素，由唯一編號(ID)、前驅(qū)弧段（PreEdges）和后繼弧段（AdjEdges）三個屬性組成。PreEdges和AdjEdges都是集合，分別記錄了該節(jié)點的所有前驅(qū)弧段和后繼弧段?；《斡肊dge類來表示，記錄了弧段連接的節(jié)點和弧段的一些基本屬性信息。整個網(wǎng)絡(luò)拓?fù)鋱D用 Graph類表示，一個關(guān)鍵的屬性是節(jié)點集合屬性，記錄所有的節(jié)點，并以哈希的方式存儲。然后創(chuàng)建兩個工作線程分別從起點和終點開始搜索。定義一個永久標(biāo)簽集合作為兩個線程的公共變量，當(dāng)其中一個線程向其添加永久節(jié)點時檢測該集合中是否存在該節(jié)點，如存在即為公共節(jié)點，結(jié)束算法；反之添加。

3.2 算法運行結(jié)果分析

傳統(tǒng)Dijkstra算法和并行二樹Dijkstra算法的執(zhí)行結(jié)果如圖3和圖4所示所示。六合路口和象山公園兩個位置的ID分別為1116和382。圖中紅色路線為六合路口到象山公園的最短路徑，藍(lán)色的點表示算法執(zhí)行過程中搜索過的結(jié)點，其節(jié)點數(shù)量反應(yīng)鄰接節(jié)點的搜索規(guī)模。

圖3 傳統(tǒng)Dijkstra求解最短路徑結(jié)果圖

圖4 并行二樹Dijkstra求解最短路徑結(jié)果圖

實驗中統(tǒng)計的結(jié)果表明，并行二樹Dijkstra算法搜索的結(jié)點數(shù)為498，相比傳統(tǒng)Dijkstra算法搜索的735結(jié)點，減少將近32%。由于并行的不可預(yù)測性，其執(zhí)行結(jié)果不是確定的，所以實驗過程中搜索的節(jié)點數(shù)也在變化，但大部分情況下其搜索的節(jié)點總數(shù)相對要少很多。

4 結(jié)束語

本文提出并行二樹Dijkstra算法可以有效的解決最短路徑問題，在車輛誘導(dǎo)系統(tǒng)中的應(yīng)用證明了該算法的實用性。但是這種優(yōu)化算法是一種以空間換取時間的算法，因為構(gòu)造了兩棵路徑搜索樹，所以會產(chǎn)生一定的附加數(shù)據(jù)，因此下一步的工作應(yīng)當(dāng)考慮如何進(jìn)一步優(yōu)化數(shù)據(jù)結(jié)構(gòu)，減少冗余數(shù)據(jù)。

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

[2] 王樹西,吳政學(xué).改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J].計算機(jī)科學(xué),2012,(5):223-228.

[3] Dantzig G B. On the shortest route through a network[J]. Management Science,1960,6(2): 187-190.

[4] Nicholson T. Finding the Shortest Route Between Two Points in a Network[J].The Computer Journal,1966, 9(3):275-280.

[5] 黃國睿,張平,魏廣博.多核處理器的關(guān)鍵技術(shù)及其發(fā)展趨勢[J].計算機(jī)工程與設(shè)計,2009,30(10):2414-2418.

[6] 王海梅.基于GIS的最優(yōu)路徑算法研究與實現(xiàn)[D].南京理工大學(xué)博士學(xué)位論文,2008:7.

Efficient implementation of Dijkstra algorithm in vehicle route guidance system based on GIS

The interdisciplinary application of intelligent transportation system comes into being just to meet people’s growing demand.The analysis of shortest path is the key problem in the application of VRGS (Vehicle Route Guidance System), the Dijkstra algorithm is the common algorithm to solve this problem effectively. Combined two-tree Dijkstra algorithm and multi-core and multi-threading technology, this paper optimizes and improves the traditional Dijkstra algorithm. And it discusses the application of the algorithm in VRGS．At last, this paper poves its practicality and efficiency by simulating the shortest path search process of Guilin.

shortest path ;Dijkstra shortest path algorithm; vehicle route guidance system

U49

A

1008-1151(2015)02-0025-04

2015-01-12

殷招偉，桂林電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院碩士，研究方向為 GIS-T應(yīng)用；戴文博，桂林電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院碩士；錢俊彥，桂林電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院博士。