最短路徑Dijkstra優(yōu)化算法在GpsOne導(dǎo)航系統(tǒng)中的研究及應(yīng)用.pdf

1、隨著計(jì)算機(jī)技術(shù)、空間技術(shù)和導(dǎo)航定位技術(shù)的迅速發(fā)展，汽車導(dǎo)航系統(tǒng)成為綜合技術(shù)應(yīng)用的熱門領(lǐng)域之一，是智能交通系統(tǒng)的重要組成部分，它不但能夠顯示電子地圖及自身的位置，而且能夠進(jìn)行信息查詢和規(guī)劃到達(dá)目的地的最優(yōu)路線，引導(dǎo)駕駛員到達(dá)目的地，從而提高道路通行率。汽車導(dǎo)航系統(tǒng)是解決現(xiàn)代交通問(wèn)題的有效方式之一。 作為汽車導(dǎo)航核心部分的最短路徑成為了關(guān)鍵問(wèn)題。Dijkstra算法是目前汽車導(dǎo)航系統(tǒng)解決最短路徑的理論基礎(chǔ)，它的優(yōu)點(diǎn)是程序設(shè)計(jì)簡(jiǎn)單、通

2、用性強(qiáng)，缺點(diǎn)是該算法對(duì)所有的數(shù)據(jù)都作循環(huán)比較，因此在數(shù)據(jù)量大的情況下，會(huì)嚴(yán)重影響計(jì)算的速度。在導(dǎo)航系統(tǒng)的最短路徑尋找中，需要尋找兩個(gè)特定點(diǎn)之間的最短或近似最短路徑，傳統(tǒng)的Dijkstra算法需要把所有的點(diǎn)都掃描一遍，導(dǎo)致算法在這方面效率不高。另外，傳統(tǒng)的Dijkstra算法采用鄰接矩陣數(shù)據(jù)結(jié)構(gòu)，占用空間比較多，浪費(fèi)計(jì)算機(jī)的資源。因此，根據(jù)實(shí)際情況對(duì)基于Dijkstra的最短路徑算法改進(jìn)是有必要的。 本文對(duì)汽車導(dǎo)航中最短路徑Dij