1、近年來，中國的快速發(fā)展雖然帶來了巨大的經(jīng)濟利益，但是隨之而來的是巨大的交通壓力。車聯(lián)網(wǎng)系統(tǒng)是提升交通效率、緩解交通擁堵的非常有效的系統(tǒng)，在車聯(lián)網(wǎng)系統(tǒng)中，導(dǎo)航系統(tǒng)是最為重要的子系統(tǒng)，而最短路徑算法部分又是導(dǎo)航系統(tǒng)中最不可或缺的組成部分。早在50多年前，最短路徑問題已經(jīng)被提出了，迄今為止，很多專家學(xué)者已經(jīng)研究分析了不同條件、不同網(wǎng)絡(luò)模型的最短路徑問題，其中當(dāng)前應(yīng)用最多的包括Dijkstra、Eiger、Kaufman和Miller-Hook

2、s等人提出的四種不同的理論模型，其中Dijkstra算法是最為經(jīng)典和成熟的算法。
　　傳統(tǒng)最短路徑算法在設(shè)計過程當(dāng)中僅考慮到網(wǎng)絡(luò)拓?fù)涮卣鳎茨芗骖櫟骄W(wǎng)絡(luò)空間分布特征，導(dǎo)致最短路徑搜索過程不具備方向性，所以會存在多個與最終查找到的最短路徑不相關(guān)節(jié)點同樣參與到計算當(dāng)中，降低了算法效率，特別是在規(guī)模較大的稀疏城市道路網(wǎng)絡(luò)當(dāng)中，所應(yīng)用到的各種算法無法有效滿足城市路網(wǎng)實時性需求。
　　首先，本論文建立了城市道路的拓?fù)淠Ｐ?，提出對城市?/p>

3、路和車輛的經(jīng)緯度計算方法，并且提煉總結(jié)出實際道路的拓?fù)涮攸c。具體包括：給出預(yù)處理經(jīng)緯度數(shù)據(jù)的方法，一方面根據(jù)城市道路中的經(jīng)緯度比較精準(zhǔn)地計算兩個節(jié)點之間的路段長度，另一方面把節(jié)點的經(jīng)緯度數(shù)據(jù)轉(zhuǎn)變?yōu)橹苯亲鴺?biāo)表示，并在此基礎(chǔ)上歸納總結(jié)出城市道路在路段長度與節(jié)點取值等方面的固有特點。
　　然后，本論文分別從兩個角度對經(jīng)典Dijkstra算法進(jìn)行優(yōu)化。在存儲方式上，闡述基于鄰接表的Dijkstra算法的實現(xiàn)方式，結(jié)果表明鄰接表比鄰接矩陣大

4、大減少了空間的占用量。在搜索區(qū)域限制上，提出橢圓搜索限制和矩形搜索限制的Dijkstra算法的搜索面積大小和確定邊界的方式，分別理論推導(dǎo)與分析它們的可靠性和有效性。最后，對優(yōu)化前后的Dijkstra算法的有效性能分別進(jìn)行數(shù)據(jù)統(tǒng)計和仿真驗證，結(jié)果表明改進(jìn)的Dijkstra算法不管是在運行速度還是占有空間上都有了很大的提高。
　　最后，本論文按照車聯(lián)網(wǎng)系統(tǒng)的基本結(jié)構(gòu)，對車載終端和云端的需求和設(shè)計方法進(jìn)行探究，然后給出了車載終端中軟件的