Dijkstra算法在停車誘導(dǎo)系統(tǒng)中的應(yīng)用

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

1 傳統(tǒng)Dijkstra算法

1.1 Dijkstra算法的原理

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

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

⑵ 從標(biāo)記為0的集合中，尋找一個(gè)距離當(dāng)前中間點(diǎn)（初始時(shí)中間點(diǎn)為源頂點(diǎn)v0）路徑最短的點(diǎn)作為新中間點(diǎn)，并標(biāo)識(shí)此點(diǎn)為1。標(biāo)記過程中，總保持從源點(diǎn)v0到標(biāo)記為1的各個(gè)頂點(diǎn)的最短路徑不大于從源點(diǎn)v0到標(biāo)記為0的頂點(diǎn)的距離。

⑶ 每個(gè)頂點(diǎn)對(duì)應(yīng)著一個(gè)距離，標(biāo)記為1的頂點(diǎn)的距離是源點(diǎn)v0到此頂點(diǎn)的最短路徑長(zhǎng)度，標(biāo)記為0的頂點(diǎn)的距離，就是源點(diǎn)v0通過標(biāo)識(shí)為1的頂點(diǎn)作為中間點(diǎn)，到達(dá)標(biāo)記為0的頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。整個(gè)算法過程是基于求出的最短路徑，在此基礎(chǔ)上，求得更遠(yuǎn)頂點(diǎn)的最短路徑，最后得到起點(diǎn)到終點(diǎn)的最終最短路徑[7]。

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

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

表1 鄰接矩陣的存儲(chǔ)結(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分別表示各頂點(diǎn)，表中的數(shù)據(jù)表示對(duì)應(yīng)兩頂點(diǎn)之間的距離，∞表示不連通。從表1中可以看出，采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)要遍歷計(jì)算所有的節(jié)點(diǎn)，但是很多節(jié)點(diǎn)都是相互不連通的，這樣就遍歷了無效的節(jié)點(diǎn)，造成了空間的大量浪費(fèi)，導(dǎo)致搜索速度慢，效率比較低。

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

2.1 存儲(chǔ)結(jié)構(gòu)的改進(jìn)

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

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

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

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

2.2 改進(jìn)算法的實(shí)現(xiàn)

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

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

改進(jìn)后的算法流程如圖1所示。

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

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

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

圖1 修改算法后的流程圖

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)過程

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

圖2 仿真實(shí)驗(yàn)的模擬地圖

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

typedef int Patharc[MAXVEX]； //存儲(chǔ)最短路徑下標(biāo)

typedef int ShortPathTable[MAXVEX]；

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

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

ShortPathTable *D） {

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

while（p！=1） //查找起點(diǎn)的所有鄰接點(diǎn)

{ if（p->ivex==v0）

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

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

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

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

p=p->ilink；

k++； }

else （p->jvex==v0） {

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

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

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

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

p=p->jlink；

k++； }}

final[v0]=1； //設(shè)置起點(diǎn)標(biāo)號(hào)為1

for（v=2； v

HeapSort（sort， k）； //進(jìn)行堆排序

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

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

sort[k]=INFINITY；

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

k--；

final[w]=1； //設(shè)置中間點(diǎn)標(biāo)號(hào)為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ù)組里沒有該頂點(diǎn)的信息，則添加*/

{ 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è)目前路徑誘導(dǎo)的起點(diǎn)是甲子立交橋（v1），目的地是湖山農(nóng)場(chǎng)作（v25），經(jīng)過本文算法求出從v1到v25的最短路徑是335（百米），最短路徑為：v1-v3-v5-v9-v13-v17-v20-v23-v25。

3.2 算法分析

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

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

表3 算法的時(shí)間復(fù)雜度對(duì)比

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

4 結(jié)束語

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

參考文獻(xiàn)：

[1] 王樹西，吳政學(xué).改進(jìn)的Dijsktra最短路徑算法及其應(yīng)用研究[J].計(jì)算

機(jī)科學(xué)，2012.39（5）：223-228

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

25（3）：30-33

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

息，2007.23（11）：275-277

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

索算法[J].北京科技大學(xué)學(xué)報(bào)，2007.29（3）：346-349

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

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

24-27

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

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

2005.8：15-17

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

件，2011.28（5）：275-277

[10] 廖遠(yuǎn).一對(duì)一最短路徑算法研究及車載導(dǎo)航系統(tǒng)設(shè)計(jì)[D].南昌大學(xué)，

2012.

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

代化，2011.1：36-38