Dijkstra算法在停車誘導系統中的應用

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

關鍵詞： 停車誘導系統； 最短路徑； Dijkstra算法； 存儲結構

中圖分類號：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 引言

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

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

1 傳統Dijkstra算法

1.1 Dijkstra算法的原理

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

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

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

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

1.2 傳統Dijkstra算法的優缺點

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

表1 鄰接矩陣的存儲結構圖

[＼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分別表示各頂點，表中的數據表示對應兩頂點之間的距離，∞表示不連通。從表1中可以看出，采用鄰接矩陣作為存儲結構要遍歷計算所有的節點，但是很多節點都是相互不連通的，這樣就遍歷了無效的節點，造成了空間的大量浪費，導致搜索速度慢，效率比較低。

2 傳統Dijkstra算法的改進

2.1 存儲結構的改進

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

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

表2 四種存儲結構的對比

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

2.2 改進算法的實現

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

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

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

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

Sort[]數組][取出權值最小的鄰接點，設為

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

圖1 修改算法后的流程圖

算法的實現步驟如下：

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

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

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

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

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

3 仿真實驗

3.1 實驗過程

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

圖2 仿真實驗的模擬地圖

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

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

typedef int ShortPathTable[MAXVEX]；

/*存儲到各點最短路徑的權值和 */

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

ShortPathTable *D） {

//…變量定義，初始化數據

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

{ if（p->ivex==v0）

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

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

/*把與v0相鄰的結點的權值放入排序數組*/

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

p=p->ilink；

k++； }

else （p->jvex==v0） {

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

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

/*把與v0相鄰的結點的權值放入排序數組*/

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

p=p->jlink；

k++； }}

final[v0]=1； //設置起點標號為1

for（v=2； v

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

w=sort[1].vertex； //設置中間點

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

sort[k]=INFINITY；

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

k--；

final[w]=1； //設置中間點標號為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數組里沒有該頂點的信息，則添加*/

{ 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； }}}}

}

}

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

3.2 算法分析

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

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

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

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

4 結束語

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

參考文獻：

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

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

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

25（3）：30-33

[3] 王志和，凌云.Dijkstra最短路徑算法的優化及其實現[J].微計算機信

息，2007.23（11）：275-277

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

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

[5] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].清華大學出版社，1997.

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

24-27

[7] 程杰.大話數據結構[M].清華大學出版社，2011.

[8] 司連法，王文靜.快速Dijkstra最短路徑優化算法的實現[J].測繪通報，

2005.8：15-17

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

件，2011.28（5）：275-277

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

2012.

[11] 郝春梅.一種改進的Dijkstra算法的分析及程序實現[J].計算機與現

代化，2011.1：36-38