資源描述：
《dijkstra算法在停車誘導(dǎo)系統(tǒng)中應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、Dijkstra算法在停車誘導(dǎo)系統(tǒng)中應(yīng)用 摘要：路徑誘導(dǎo)是停車誘導(dǎo)系統(tǒng)中需要解決的關(guān)鍵問題，而路徑誘導(dǎo)的本質(zhì)就是求最短路徑，Dijkstra算法可以很好地求解最短路徑。傳統(tǒng)Dijkstra算法采用鄰接矩陣作為存儲結(jié)構(gòu)，算法的時(shí)間復(fù)雜度為O（n2），存在搜索速度慢和浪費(fèi)空間的缺點(diǎn)。為此，對傳統(tǒng)Dijkstra算法進(jìn)行了改進(jìn)，采用鄰接多重表作為存儲結(jié)構(gòu)，采用堆排序法的思想來尋找權(quán)值最小的頂點(diǎn)，算法的時(shí)間復(fù)雜度為O（nlog2n）。用改進(jìn)后的算法在實(shí)際地圖中進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，改進(jìn)后的算法能更快、更有效率地找到兩點(diǎn)間的最短路
2、徑。關(guān)鍵詞：停車誘導(dǎo)系統(tǒng)；最短路徑；Dijkstra算法；存儲結(jié)構(gòu)中圖分類號：TP301.6文獻(xiàn)標(biāo)志碼：A文章編號：1006-8228（2013）12-38-03ApplicationofDijkstraalgorithminparkingguidancesystemHuangZhen，XueWenke，LiPeng，LiJianping（DepartmentofComputerScience，HuizhouUniversity，Huizhou，Guangdong516007，China）Abstract：Therouteg
3、uidanceisthekeyproblem14intheparkingguidancesystemandtheessenceoftherouteguidanceistosettledowntheproblemoftheshortestpath.TheDijkstraalgorithmisaperfectmethodtoworkitout.ThetraditionalalgorithmappliesadjacencymatrixasitsstoragestructureanditstimecomplexityisO（n2）.
4、Howeverthiskindofalgorithmhasdisadvantagesinlowefficiencyandwastingspace.ItisimprovedbytakingadjacencymultilistasthestoragestructureandalteringthetimecomplexityintoO（nlog2n），whichhasturnedouttobemoreefficientandeffectivetofindouttheshortestpathinthesimulationexperi
5、mentofrealmap.Keywords：parkingguidancesystem；theshortestpath；Dijkstraalgorithm；storagestructure0引言14停車誘導(dǎo)系統(tǒng)是智能交通系統(tǒng)的一個(gè)重要組成部分，隨著我國汽車產(chǎn)業(yè)的迅猛發(fā)展，越來越多的人開始投入到停車誘導(dǎo)系統(tǒng)方面的研究開發(fā)中。停車誘導(dǎo)系統(tǒng)中的核心問題路徑誘導(dǎo)其實(shí)就是求解最短路徑問題。目前對最短路徑問題的研究有很多，在大量的最短路徑算法中，Dijkstra算法是最經(jīng)典的方法，有許多學(xué)者對Dijkstra算法進(jìn)行優(yōu)化來求解最短路徑
6、問題。王樹西等[1]提出了修改標(biāo)記法，解決了傳統(tǒng)Dijkstra算法的退出機(jī)制在有向圖中如果兩點(diǎn)不連通而陷入死循環(huán)的問題。章永龍[2]提出只對最短路徑上節(jié)點(diǎn)的鄰居做處理，不考慮其他節(jié)點(diǎn)，來減少計(jì)算節(jié)點(diǎn)的數(shù)量，提高算法速度。王志和等[3]提出采用配對堆結(jié)構(gòu)來實(shí)現(xiàn)路徑計(jì)算過程中優(yōu)先級隊(duì)列的一系列操作。王景存等[4]在Dijkstra算法基礎(chǔ)上將決策機(jī)制運(yùn)入到路徑搜索中，提出一種啟發(fā)式最優(yōu)路徑搜索算法。傳統(tǒng)Dijkstra算法采用鄰接矩陣存儲結(jié)構(gòu)，這在實(shí)際的交通網(wǎng)絡(luò)上求解最短路徑時(shí)，會造成空間的大量浪費(fèi)，而且搜索速度慢，不能達(dá)到應(yīng)
7、用的需求。本文在Dijkstra算法基礎(chǔ)上采用鄰接多重表存儲結(jié)構(gòu)，在實(shí)際地圖中進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，搜索速度大大優(yōu)于采用鄰接矩陣的傳統(tǒng)Dijkstra算法。1傳統(tǒng)Dijkstra算法1.1Dijkstra算法的原理Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra在1959年提出的一種求單源最短路徑的算法，即選定一個(gè)起始點(diǎn)，計(jì)算起始點(diǎn)到其他點(diǎn)的最短路徑的算法。其算法原理[5-6]如下。⑴14設(shè)有一個(gè)帶權(quán)有向圖G（V，E），把該圖的頂點(diǎn)集合分成兩組，一組為已經(jīng)算出最短路徑的頂點(diǎn)的集合（頂點(diǎn)標(biāo)記為1，開始時(shí)該集合
8、為空），另一組則為還沒有涉及到的頂點(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)識此點(diǎn)為1。標(biāo)記過程中，總保持從源點(diǎn)v0到標(biāo)記為1的各個(gè)頂點(diǎn)的最短路徑不大于從源點(diǎn)v0到標(biāo)記為0的頂點(diǎn)
