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

殷招偉 戴文博 錢俊彥

（桂林電子科技大學計算機科學與工程學院，廣西 桂林 541004）

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

殷招偉 戴文博 錢俊彥

（桂林電子科技大學計算機科學與工程學院，廣西 桂林 541004）

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

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

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

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

1 Dijkstra算法

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

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

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

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

2.1 二樹Dijkstra算法

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

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

2.2 二樹Dijkstra算法的改進

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

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

圖1 算法搜索范圍示意圖

2.3 測試結果與分析

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

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

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

3 并行二樹 Dijkstra算法在 VRGS中的應用

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

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

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

3.2 算法運行結果分析

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

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

圖4 并行二樹Dijkstra求解最短路徑結果圖

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

4 結束語

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

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

[2] 王樹西,吳政學.改進的Dijkstra最短路徑算法及其應用研究[J].計算機科學,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] 黃國睿,張平,魏廣博.多核處理器的關鍵技術及其發(fā)展趨勢[J].計算機工程與設計,2009,30(10):2414-2418.

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

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