摘 要： 路徑誘導是停車誘導系統(tǒng)中需要解決的關(guān)鍵問題，而路徑誘導的本質(zhì)就是求最短路徑，Dijkstra算法可以很好地求解最短路徑。傳統(tǒng)Dijkstra算法采用鄰接矩陣作為存儲結(jié)構(gòu)，算法的時間復雜度為O（n2），存在搜索速度慢和浪費空間的缺點。為此，對傳統(tǒng)Dijkstra算法進行了改進，采用鄰接多重表作為存儲結(jié)構(gòu)，采用堆排序法的思想來尋找權(quán)值最小的頂點，算法的時間復雜度為O（nlog2n）。用改進后的算法在實際地圖中進行仿真實驗，結(jié)果表明，改進后的算法能更快、更有效率地找到兩點間的最短路徑。

關(guān)鍵詞： 停車誘導系統(tǒng)； 最短路徑； Dijkstra算法； 存儲結(jié)構(gòu)

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1006-8228（2013）12-38-03

Application of Dijkstra algorithm in parking guidance system

Huang Zhen， Xue Wenke， Li Peng， Li Jianping

（Department of Computer Science， Huizhou University， Huizhou， Guangdong 516007， China）

Abstract： The route guidance is the key problem in the parking guidance system and the essence of the route guidance is to settle down the problem of the shortest path. The Dijkstra algorithm is a perfect method to work it out. The traditional algorithm applies adjacency matrix as its storage structure and its time complexity is O（n2）. However this kind of algorithm has disadvantages in low efficiency and wasting space. It is improved by taking adjacency multilist as the storage structure and altering the time complexity into O（nlog2n）， which has turned out to be more efficient and effective to find out the shortest path in the simulation experiment of real map.

Key words： parking guidance system； the shortest path； Dijkstra algorithm； storage structure

0 引言

停車誘導系統(tǒng)是智能交通系統(tǒng)的一個重要組成部分，隨著我國汽車產(chǎn)業(yè)的迅猛發(fā)展，越來越多的人開始投入到停車誘導系統(tǒng)方面的研究開發(fā)中。停車誘導系統(tǒng)中的核心問題路徑誘導其實就是求解最短路徑問題。目前對最短路徑問題的研究有很多，在大量的最短路徑算法中，Dijkstra算法是最經(jīng)典的方法，有許多學者對Dijkstra算法進行優(yōu)化來求解最短路徑問題。王樹西等[1]提出了修改標記法，解決了傳統(tǒng)Dijkstra算法的退出機制在有向圖中如果兩點不連通而陷入死循環(huán)的問題。章永龍[2]提出只對最短路徑上節(jié)點的鄰居做處理，不考慮其他節(jié)點，來減少計算節(jié)點的數(shù)量，提高算法速度。王志和等[3]提出采用配對堆結(jié)構(gòu)來實現(xiàn)路徑計算過程中優(yōu)先級隊列的一系列操作。王景存等[4]在Dijkstra算法基礎(chǔ)上將決策機制運入到路徑搜索中，提出一種啟發(fā)式最優(yōu)路徑搜索算法。

傳統(tǒng)Dijkstra算法采用鄰接矩陣存儲結(jié)構(gòu)，這在實際的交通網(wǎng)絡上求解最短路徑時，會造成空間的大量浪費，而且搜索速度慢，不能達到應用的需求。本文在Dijkstra算法基礎(chǔ)上采用鄰接多重表存儲結(jié)構(gòu)，在實際地圖中進行仿真實驗，結(jié)果表明，搜索速度大大優(yōu)于采用鄰接矩陣的傳統(tǒng)Dijkstra算法。

1 傳統(tǒng)Dijkstra算法

1.1 Dijkstra算法的原理

Dijkstra算法是由荷蘭計算機科學家E.W.Dijkstra在1959年提出的一種求單源最短路徑的算法，即選定一個起始點，計算起始點到其他點的最短路徑的算法。其算法原理[5-6]如下。

⑴ 設(shè)有一個帶權(quán)有向圖G（V，E），把該圖的頂點集合分成兩組，一組為已經(jīng)算出最短路徑的頂點的集合（頂點標記為1，開始時該集合為空），另一組則為還沒有涉及到的頂點的集合（頂點標記為0，開始時全部頂點都標記為0）。

⑵ 從標記為0的集合中，尋找一個距離當前中間點（初始時中間點為源頂點v0）路徑最短的點作為新中間點，并標識此點為1。標記過程中，總保持從源點v0到標記為1的各個頂點的最短路徑不大于從源點v0到標記為0的頂點的距離。

⑶ 每個頂點對應著一個距離，標記為1的頂點的距離是源點v0到此頂點的最短路徑長度，標記為0的頂點的距離，就是源點v0通過標識為1的頂點作為中間點，到達標記為0的頂點的當前最短路徑長度。整個算法過程是基于求出的最短路徑，在此基礎(chǔ)上，求得更遠頂點的最短路徑，最后得到起點到終點的最終最短路徑[7]。

1.2 傳統(tǒng)Dijkstra算法的優(yōu)缺點

傳統(tǒng)的Dijkstra 算法采用鄰接矩陣的存儲結(jié)構(gòu)，是最短路徑的最經(jīng)典的算法，既可以用于有向圖，也可以用于無向圖，其優(yōu)點是算法原理簡單，實現(xiàn)起來比較容易，缺點是搜索速度慢和浪費空間。例如一個存在7個節(jié)點的無向圖，其鄰接矩陣如表1所示。

表1 鄰接矩陣的存儲結(jié)構(gòu)圖

[＼1＼2＼3＼4＼5＼6＼7＼1＼0＼45＼32＼80＼∞＼∞＼∞＼2＼45＼0＼∞＼∞＼21＼∞＼∞＼3＼32＼∞＼0＼∞＼45＼∞＼93＼4＼80＼∞＼∞＼0＼∞＼∞＼79＼5＼∞＼21＼45＼∞＼0＼44＼∞＼6＼∞＼∞＼∞＼∞＼44＼0＼50＼7＼∞＼∞＼93＼79＼∞＼50＼0＼]

在表1中，1至7分別表示各頂點，表中的數(shù)據(jù)表示對應兩頂點之間的距離，∞表示不連通。從表1中可以看出，采用鄰接矩陣作為存儲結(jié)構(gòu)要遍歷計算所有的節(jié)點，但是很多節(jié)點都是相互不連通的，這樣就遍歷了無效的節(jié)點，造成了空間的大量浪費，導致搜索速度慢，效率比較低。

2 傳統(tǒng)Dijkstra算法的改進

2.1 存儲結(jié)構(gòu)的改進

Dijkstra算法的存儲結(jié)構(gòu)通常是采用鄰接矩陣，鄰接矩陣空間利用率比較低，而且不容易表示圖中頂點間的關(guān)系。一般在編程時采用數(shù)組來表示鄰接矩陣，在實際應用的地圖中表示鄰接矩陣的數(shù)組會含有大量的0和∞的數(shù)組元素，在程序中遍歷數(shù)組元素時會執(zhí)行很多無效的語句，使得程序的效率很低，這樣會不利于提升算法的搜索速度[8-9]。

常用的表示圖形的存儲結(jié)構(gòu)有四種，四種存儲結(jié)構(gòu)的對比如表2所示[10]，在表2中表示時間復雜度的n是圖的頂點數(shù)，m是圖的邊數(shù)。由表2可知四種存儲結(jié)構(gòu)各有優(yōu)缺點，其中鄰接表雖然操作簡單，但是構(gòu)圖的時間復雜度是O（n2）， 鄰接多重表構(gòu)圖的時間復雜度是O（n+m）?，F(xiàn)代存儲技術(shù)發(fā)展迅速，存儲空間已經(jīng)不再成為一個瓶頸，我們應首先考慮時間復雜度，再考慮空間復雜度。另外，在實際的路徑誘導地圖中一般采用無向圖表示，用鄰接多重表對無向圖的操作也比其他存儲結(jié)構(gòu)更方便，而且鄰接多重表的搜索速度是最快的。綜合以上因素，本文在求解最短路徑問題時選取鄰接多重表作為Dijkstra算法的存儲結(jié)構(gòu)。

表2 四種存儲結(jié)構(gòu)的對比

[存儲結(jié)構(gòu)＼優(yōu)點＼缺點＼時間復雜度＼鄰接矩陣＼操作簡單，計算方便＼搜索費時，浪費空間＼O（n2）＼鄰接鏈表＼搜索速度快，節(jié)省空間＼操作復雜＼O（n+m）＼鄰接多重表＼搜索速度最快＼占存儲空間，操作復雜＼O（n+m）＼索引表格＼計算方便，操作簡單＼浪費空間＼O（n+m）＼]

2.2 改進算法的實現(xiàn)

本文首先將實際地圖抽象為無向圖，然后采用鄰接多重表來存儲該無向圖，具體實現(xiàn)如下：對無向圖的每一條邊用鄰接多重表的一個結(jié)點表示，它由六個域組成，分別是mark、ivex、ilink、jvex、jlink、info，其中mark標記該邊是否已經(jīng)遍歷，ivex和jvex為該邊依附的兩個頂點在圖中的位置，ilink指向下一條依附于頂點ivex的邊，jlink指向下一條依附于頂點jvex的邊，info為指向和邊相關(guān)的各種信息的指針域。每個頂點也用一個結(jié)點表示，它由data、firstedge兩個域組成，其中，data域儲存和該頂點相關(guān)的信息，firstedge域指示第一條依附于該頂點的邊。

根據(jù)Dijkstra算法的原理，提高選取中間點的速度可以改進算法的效率。為了提高選取中間點的效率，可以對標記為0的結(jié)點與當前中間點的權(quán)值進行排序，在節(jié)點數(shù)較少的情況下不排序操作會簡單些，時間也相對較少，但在節(jié)點數(shù)量比較大的時候，時間復雜度會隨著要遍歷的節(jié)點數(shù)的增加而大幅度增加。本文參考了文獻[11]的方法，采用堆排序的思想在標記為0的節(jié)點中找到權(quán)值最小的節(jié)點作為中間點，可以提高選取中間點的速度，從而改進算法的效率。

改進后的算法流程如圖1所示。

[是否在Sort[]數(shù)組里][起點開始][尋找鄰接點][加入Sort[]數(shù)組] [鄰接點是否全部加入

Sort[]數(shù)組][取出權(quán)值最小的鄰接點，設(shè)為

中間點，并把該節(jié)點標記為1] [是否在D[]中記錄][看此時的權(quán)值是否比之前記錄的小，小的話就更新，不是就不改動] [判斷標號1的節(jié)點數(shù)是否等于n總節(jié)點數(shù)][結(jié)束][記錄相應的權(quán)值] [否][以w為中間點] [否] [是][否][是][是] [否] [是]

圖1 修改算法后的流程圖

算法的實現(xiàn)步驟如下：

⑴ 所有節(jié)點標記為0，從起點v1開始尋找它的鄰接點，將起點標記為1；

⑵ 判斷尋找到的鄰接點是否在排序數(shù)組Sort中，如果在數(shù)組中則轉(zhuǎn)到步驟⑴，尋找下一個鄰接點，如果不在數(shù)組Sort中，則把這個鄰接點加入Sort數(shù)組；

⑶ 判斷是否所有鄰接點都加入Sort[]數(shù)組里，如果不是則轉(zhuǎn)到步驟⑴，尋找下一個鄰接點，如果是則繼續(xù)步驟⑷；

⑷ 采用堆排序的思想在排序數(shù)組Sort中選出權(quán)值最小的鄰接點作為中間點w，并標記為1，接著取出與w相鄰節(jié)點的權(quán)值，判斷在D數(shù)組里有沒有與w相鄰節(jié)點權(quán)值的記錄，若沒有則加入D數(shù)組中，若有則比較權(quán)值大小，將權(quán)值小的記錄更新D數(shù)組。數(shù)組D用于記錄起點v1到所有鄰接點的權(quán)值；

⑸ 判斷被標記為1的節(jié)點數(shù)是否等于要遍歷的總節(jié)點數(shù)n，若否，則以w為中間點，繼續(xù)遍歷它的鄰接點，重復上面的步驟，若是，則表示每個節(jié)點都遍歷完，算法結(jié)束。

3 仿真實驗

3.1 實驗過程

本實驗的數(shù)據(jù)采用惠城區(qū)的模擬地圖，模擬地圖如圖2所示，圖2中的頂點之間距離單位為百米，為了計算方便，在此對距離數(shù)據(jù)進行了取整。

圖2 仿真實驗的模擬地圖

本文算法首先將模擬地圖抽象為無向圖（25個節(jié)點，48條邊），用鄰接多重表來構(gòu)建無向圖G，采用Dijkstra算法可以求出任意起點到其他所有節(jié)點的最短路徑，改進算法的關(guān)鍵代碼如下：

typedef int Patharc[MAXVEX]； //存儲最短路徑下標

typedef int ShortPathTable[MAXVEX]；

/*存儲到各點最短路徑的權(quán)值和 */

void ShortestPath_Dijkstra（MGraph G， int v0， Patharc *Pre，

ShortPathTable *D） {

//…變量定義，初始化數(shù)據(jù)

while（p！=1） //查找起點的所有鄰接點

{ if（p->ivex==v0）

{ （*D）[p->jvex]=p->data；

Addtosort（k，p->jvex，（*D）[p->jvex]）；

/*把與v0相鄰的結(jié)點的權(quán)值放入排序數(shù)組*/

mark[p->jvex]=1； //標記頂點已放入排序數(shù)組

p=p->ilink；

k++； }

else （p->jvex==v0） {

（*D）[p->ivex]=p->data；

Addtosort（k，p->ivex，（*D）[p->ivex]）；

/*把與v0相鄰的結(jié)點的權(quán)值放入排序數(shù)組*/

mark[p->ivex]=1； //標記頂點已放入排序數(shù)組

p=p->jlink；

k++； }}

final[v0]=1； //設(shè)置起點標號為1

for（v=2； v

HeapSort（sort， k）； //進行堆排序

w=sort[1].vertex； //設(shè)置中間點

Swap（sort[1]， sort[k]）；

sort[k]=INFINITY；

mark[w]=0； //將中間點從排序數(shù)組移除

k--；

final[w]=1； //設(shè)置中間點標號為1

p=G.adjlist[w].firstedge；

while（p！=1） {

if（p->ivex==w） {

if（（final[p->jvex]==0）（（*D）[w]+p->data<（*D）[p->jvex]）） {

（*D）[p->jvex]=（*D）[w]+p->data；

Pre[p->jvex]=w；

if（mark[p->jvex]！=1）

/*如果sort數(shù)組里沒有該頂點的信息，則添加*/

{ k++；

Addtosort（k，p->jvex，（*D）[p->jvex]） }

else

UpdateSort（p->jvex，（*D）[p->jvex]）；

p=p->ilink； }

else if（p->jvex==w）

{ if（final[p->ivex]==0）（（*D）[w]+p->data<（*D）

[p->ivex]）） {

（*D）[p->ivex]=（*D）[w]+p->data；

Pre[p->ivex]=w；

if（mark[p->ivex]！=1） {

k++；

Addtosort（k，p->jvex，（*D）[p->ivex]）； }

else

UpdateSort（p->jvex，（*D）[p->ivex]）；

p=p->jlink； }}}}

}

}

假設(shè)目前路徑誘導的起點是甲子立交橋（v1），目的地是湖山農(nóng)場作（v25），經(jīng)過本文算法求出從v1到v25的最短路徑是335（百米），最短路徑為：v1-v3-v5-v9-v13-v17-v20-v23-v25。

3.2 算法分析

求解最短路徑時，首先需要在程序中構(gòu)建圖的結(jié)構(gòu)，采用鄰接表的Dijkstra算法構(gòu)建圖的時間復雜度是O（n2），改進后的算法采用鄰接多重表來構(gòu)建無向圖的時間復雜度O（n+m）。在實際地圖中，一般節(jié)點數(shù)n都比較大，而邊數(shù)m遠小于n2的數(shù)量級，所以采用鄰接多重表的改進算法將大大提高構(gòu)建圖的效率。

改進后算法的求解時間主要消耗在兩個方面，一是查找中間點，二是在中間點的鄰接點中找出從起點經(jīng)過中間點到該鄰接點的更小的權(quán)值和。查找中間點時，本文算法采用堆排序的思想找出最小權(quán)值的節(jié)點作為中間點，一趟堆排序的時間復雜度為O（log2n）；找中間點的鄰接點時，由于算法采用的是鄰接多重表存儲圖，每個節(jié)點的所有鄰接邊都在同一個鏈表中，所以每次遍歷次數(shù)是當前節(jié)點的鄰接邊的條數(shù)e；而這兩個過程的外循環(huán)都遍歷了所有節(jié)點，都是需要循環(huán)n次。所以改進算法最壞的時間復雜度為O（n*（log2n+e）），但是在實際地圖中每個點的鄰接邊數(shù)e都很少，遠小于圖的節(jié)點數(shù)n，因此在求解實際地圖的最短路徑問題時本文算法的時間復雜度可以認為是O（n log2n）。傳統(tǒng)Dijkstra算法和本文算法的時間復雜度對比如表3所示。

表3 算法的時間復雜度對比

[算法＼構(gòu)建圖的時間復雜度＼求最短路徑時間復雜度＼鄰接表的Dijkstra算法＼O（n2）＼O（n2）＼改進算法＼O（n+m）＼O（nlog2n）＼]

4 結(jié)束語

本文在分析了傳統(tǒng)Dijkstra算法的基礎(chǔ)上，對Dijkstra算法的存儲結(jié)構(gòu)進行了分析，采用鄰接多重表來構(gòu)建無向圖，優(yōu)化了構(gòu)建無向圖和求解最短路徑問題的時間復雜度。用C++實現(xiàn)了改進的算法并在模擬地圖上仿真實驗，實驗表明，改進算法能夠快速找到起點到目的地的最短路徑。

參考文獻：

[1] 王樹西，吳政學.改進的Dijsktra最短路徑算法及其應用研究[J].計算

機科學，2012.39（5）：223-228

[2] 章永龍.Dijkstra最短路徑算法優(yōu)化[J].南昌工程學院學報，2006.

25（3）：30-33

[3] 王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實現(xiàn)[J].微計算機信

息，2007.23（11）：275-277

[4] 王景存，張曉彤，陳彬等.一種基于Dijkstra算法的啟發(fā)式最優(yōu)路徑搜

索算法[J].北京科技大學學報，2007.29（3）：346-349

[5] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學出版社，1997.

[6] 張勤.Dijkstra最短路徑算法的C語言實現(xiàn)[J].福州大學學報，2011.4：

24-27

[7] 程杰.大話數(shù)據(jù)結(jié)構(gòu)[M].清華大學出版社，2011.

[8] 司連法，王文靜.快速Dijkstra最短路徑優(yōu)化算法的實現(xiàn)[J].測繪通報，

2005.8：15-17

[9] 張成花.GIS中一種改進的Dijsktra算法及其實現(xiàn)[J].計算機應用與軟

件，2011.28（5）：275-277

[10] 廖遠.一對一最短路徑算法研究及車載導航系統(tǒng)設(shè)計[D].南昌大學，

2012.

[11] 郝春梅.一種改進的Dijkstra算法的分析及程序?qū)崿F(xiàn)[J].計算機與現(xiàn)

代化，2011.1：36-38