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

殷招偉 戴文博 錢俊彥

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

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

殷招偉 戴文博 錢俊彥

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

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

最短路徑；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]，其核心問(wèn)題是求解最短路徑問(wèn)題。最短路徑問(wèn)題是指在一定的評(píng)判準(zhǔn)則下，尋找源點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的最優(yōu)路徑[1]。

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

1 Dijkstra算法

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

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

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

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

2.1 二樹Dijkstra算法

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

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

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

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

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

圖1 算法搜索范圍示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文提出并行二樹Dijkstra算法可以有效的解決最短路徑問(wèn)題，在車輛誘導(dǎo)系統(tǒng)中的應(yīng)用證明了該算法的實(shí)用性。但是這種優(yōu)化算法是一種以空間換取時(shí)間的算法，因?yàn)闃?gòu)造了兩棵路徑搜索樹，所以會(huì)產(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].測(cè)繪與空間地理信息,2011,(4):129-131.

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

[6] 王海梅.基于GIS的最優(yōu)路徑算法研究與實(shí)現(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ì)算機(jī)科學(xué)與工程學(xué)院碩士，研究方向?yàn)?GIS-T應(yīng)用；戴文博，桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士；錢俊彥，桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院博士。