Dijkstra算法的改進及其在車輛導航系統中的應用

郭春樺

摘 要：本文分別闡述傳統Dijkstra算法和改進Dijkstra算法的算法思想，并在仿真實驗中比較這兩個算法在實際應用中的效果，用具體數據證明改進Dijkstra算法能更好的解決當前交通擁堵問題。

關鍵詞：Dijkstra算法；最短路徑；最優路徑；帶權圖；車輛導航

1 引言

隨著我國經濟的快速發展，很多家庭都擁有汽車，私家車數量的劇增，使得交通路況惡化，交通擁堵現象越來越嚴重。這給居民的出行帶來了極大的不便，嚴重影響了我們的工作生活。為了解決交通擁堵的問題，各相關部門采取了很多措施，增派交警到關鍵路段指揮，車輛限行政策，甚至是增加道路基礎設施建設，但這些措施要么收效甚微，要么成本昂貴。這種情況下，各國紛紛致力于新興交通科技的研究，以應對目前嚴峻的交通環境。車輛導航系統就是其中最重要的一項技術，它通過向駕駛員提供到達目的地的最優路徑來引導駕駛員行駛，縮短車輛在道路上的停留時間，進而減少擁堵，改善交通情況。

2 最優路徑的內涵

對于車輛導航的研究，為駕駛者選擇一條最好的路徑是關鍵。人們剛開始關注的是基于已有道路基礎的從當前位置到目標地點路程最短的路徑，這種路徑是靜態不變。但在現實應用中，由于交通情況是不斷變化的，兩點間路程最短并不表示出行時間最短，當最短路徑擁堵時，路程長的路徑可能反倒耗時短。因此最優路徑必須將實時交通流的分布狀況和其他因素加入到考慮分析中，選擇行駛時間最短的路徑，更能滿足實際的需要，這種時間最短的路徑，是基于實時交通信息的、是動態的。

3 Dijkstra算法求路程最短路徑

Dijkstra算法是目前求解最短路徑問題的理論上最完備、應用最廣泛的經典算法，它可以求出帶權圖中指定頂點到圖中其他所有頂點的最短路徑。其基本思想是按路徑長度遞增的次序產生最短路徑：

把圖中所有頂點V分成兩組：

⑴S：已求出最短路徑的頂點的集合

⑵T=V-S：尚未確定最短路徑的頂點集合

依據起點v到T中頂點vk的最短路徑，要么是從v到vk的直接路徑的權值，要么是從v經S中頂點到vk的路徑權值之和，將T中頂點按最短路徑遞增的次序加入到S中。

那么，現在只要把交通路網抽象成一個帶權圖，就可以利用Dijkstra算法確定兩地間的最短路徑，具體規定如下：

⑴頂點：道路的交叉口或端點

⑵弧：兩頂點之間的路段（含有方向）

⑶弧的權：路段長度

⑷路段上的任一地點依靠其最近的頂點。

4 改進Dijkstra算法求基于實時交通信息的時間最短路徑——最優路徑

4.1 影響行駛時間的因素有哪些

⑴擁堵情況；

⑵紅綠燈的延誤時間；

4.2 把影響因素按照一定標準進行量化

對于擁堵情況，我國公布的《城市交通管理評價指標體系》中規定，用城市路上機動車的平均行駛速度來描述起交通擁堵程度：⑴暢通：不低于30km/h；⑵輕度擁擠：20～30km/h；⑶擁擠：10～20km/h；⑷嚴重擁擠：低于10km/h。這樣就能根據路段長度和平均行駛速度計算得到該路段的行駛時間。對于紅綠燈，直接把延誤時間作為度量標準。這些實時數據，可以通過各種交通服務設施獲得，如環形線圈檢測器等。

4.3 將城市路網抽象，建立相關網絡模型

⑴頂點V：道路交叉口或端點

⑵頂點的權Wv：紅綠燈延誤時間

⑶弧R：兩頂點間的路段

⑷弧的權Wr：路段需要的行駛時間

⑸路段上的任一地點依靠其最近的頂點。

傳統的Dijkstra算法中，頂點是不含權重的，但我們確定最短時間路徑時，交叉口的時間延誤必須考慮在內，所以頂點是有權值的。

4.4 在上述網絡模型中求時間最短路徑的算法

根據以上分析，為了求時間最短路徑，改進的Dijkstra算法描述如下：

⑴假設用帶權鄰接矩陣arcs表示帶權有向圖，arcs[i][j]表示弧的權，若弧不存在，則權值為∞；用向量W表示頂點的權，W[i]表示頂點vi的權值；S表示已求出最短路徑的頂點的集合，初態為空；V-S表示尚未確定最短路徑的頂點集合，初態為全部頂點；向量D，它的每個分量D[i]表示從始點v到每個終點vi的最短路徑的長度，初態為：

⑵取vj，使得

vj就是當前求得的一條從v出發的最短路徑的終點，令

⑶修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度，如果

則修改D[k]為

⑷重復操作（2）（3），直到求出到指定頂點的最短路徑。

⑸仿真實驗

下面以一個模擬路網為例，說明路程行駛時間和最優路徑求解方法。

圖1表示按傳統方法抽象的交通路網，這里，弧上的權表示路程（單位km），為了簡化示意圖，直線表示雙行線，箭頭表示單行線。

取得實時交通信息之后，計算出每段路程所需的行駛時間，并添加紅綠燈延誤時間，得到新的帶權有向圖（圖2），其中，弧上的權表示所需行駛時間，頂點中的權表示紅綠燈延誤時間，單位分鐘。

1）假設始點是v，目標地點是v5，傳統Dijkstra算法執行過程：

求出v到達v5的路程最短路徑為v—v3—v2—v5，路程長度為12km。

2）改進Dijkstra算法算法執行過程：

求出v到達v5的行駛時間最短路徑為v—v1—v5，所需行駛時間為15分鐘，而傳統Dijkstra算法求出的路徑在相同的交通情況中需要時間31分鐘，實驗數據表明，改進的Dijkstra算法求得的路徑雖然路程比較遠（21km），但由于只要經過一個紅綠燈，延誤時間少，而且，路況良好，車流比較順暢，所以所需行駛時間比傳統Dijkstra算法求得的路徑少了許多，這種方案更能滿足用戶的實際需要，而且引導駕駛者避免擁擠的路段，選擇車流相對順暢的路段，更能解決交通擁堵的問題。

[參考文獻]

[1]賀正兵，關偉.考慮信號交叉口影響的分散路徑誘導策略[J].北京工業大學學報，2013（10）.

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

[3]王一松.基于實時交通信息的最優路徑規劃算法研究[J].計算機與現代化，2013（2）.

[4]衛瑋.基于實時交通信息的最優路徑算法研究與實現[D].長安大學.2009.

[5]翟振，孫鑫，李志鋒.基于Dijkstra算法的車輛導航系統路線優化技術[J].測繪科學.2008（S1）.

[6]李妍峰.基于實時交通信息的城市動態網絡車輛路徑優化問題[J].系統工程理論與實踐.2013（7）.

[7]田明星.路徑規劃在車輛導航系統中的應用研究[D].北京交通大學. 2009.

[8]李進燕.基于簡化路網模型的行程時間預測及導航算法研究[D].重慶大學.2012.