最短路徑迪杰斯特拉（Dijkstra）算法的優化

摘 要：Dijkstra算法是在道路網中選取最短路徑，這是一個事先的選擇過程，是理想的靜止狀態下的計算，所得的最短路徑在現實中往往不會是最佳的路徑。在車輛實際運行中，路況信息也就是道路權重值是隨時動態變化的，這就要求能對最短路徑進行重新的計算。針對Dijkstra算法存在的弊端，本文利用動態最短路徑搜索方法進行了優化改進。

關鍵詞：Dijkstra算法；最短路徑；優化

1 Dijkstra算法分析

Dijkstra算法的計算是從路段長度的集合S中進行最短路徑的對比選取，算法的速度與集合S的大小有直接的關系。城市的道路網中從V到Vi的最短路徑為d（V，Vi），則d（V，Vi）中包含了所有滿足d（V，r）< d（V，Vi）的頂點r，也就是集合S。在這個算法中，不僅僅計算了點V到Vi的最短路徑，而且也計算得出了V到S集合中全部頂點的最短路徑，這就產生了大量的無用頂點r，集合S越大則所需要計算的頂點r的數量越多，所占用的時間也就越多。如果城市的道路網比較大，兩目的地之間的距離越遠，在Dijkstra算法中所計算的頂點r甚至會遍布城市道路網中所有的頂點，這就增加了算法的額外運算量，降低了效率。

2 Dijkstra算法改進

現在的城市救援車輛基本上已經全部安裝了GPS定位裝置，可以實時的確定車輛的位置，這就為動態最短路徑搜索方法的實現提供了設備上的支持。

動態最短路徑搜索方法簡單來說就是在車輛運行過程中，根據實時的車輛位置和路況信息進行最短路徑的搜索，它的搜索范圍僅局限在車輛所在位置周圍一定的距離。在這種算法中雖然有固定的起點和目的地，但是在路徑的選取中主要是根據車輛在道路上實際運行情況來確定每段道路的終點，也就是將起點與最終的目的地之間劃分成一個個的短的區間，求解每個區間之間的最短路徑。在車輛實際運行中經常會遇到兩種情況：一種是車輛偏離預定路線比如走錯路轉錯方向，無法按照預定的路線行駛；另一種是在車輛運行中路況發生變化如發生擁堵，在動態最短路徑選擇的方法下可以很好的解決此類問題。

動態最短路徑搜索方法具有很大的靈活性和實用性，它的搜索范圍僅在車輛周圍所涉及的道路節點長度信息要比Dijkstra算法中少得多，因此計算所用的時間要短的多，而且所的到的最終路徑可以認為是一條最佳的路徑。

本文在動態最短路徑選擇方法下對Dijkstra算法進行了優化改進。

在該方法中首先要確定一個車輛道路通行時間的計算公式，本文采用如下公式進行計算：

（1）

式中：

--車輛在a路段的通行時間；

--a路段的長度；

--車輛平均車速；

α、β--道路參數；

--a路段的交通流量；

--單位時間內a路段最大通過車輛數。

改進后的計算方法步驟如下：

（1）將道路網數據進行劃分

將起點V與目的地Vi之間的路段劃分成n個區域，n的取值由兩點之間的直線距離決定，距離越遠n越大。劃分成n個區域后，按照一定的范圍將每個區域內的所有路段長度用集合Dn（li）分別存儲。

（2）提取道路通行時間最短的路段

先在第一個路段區域內的路段長度集合D1（li）中，運用上述公式（1）計算得出每段路當前路況下的通行時間[ti]，將[ti]按照時間的長短進行序列排隊，則通行時間最短的ta所代表的路段a就是最佳的路徑選擇。依次類推可以求的n個區域內的n條最佳路徑。

（3）動態調節

車輛由上步確定的第一條最佳路徑出發后，根據車輛GPS的實時定位信息和實際的車輛運行情況進行路徑的動態調節。如果沒有遇到影響通行時間的情況，車輛就按照既定的路線行駛。當車輛在道路行駛中遇到擁堵或偏移預定路線的情況時，將此時GPS定位的車輛位置點作為新的出發點，重復（1）操作重新進行區域劃分，然后實施步驟（2），計算新的最佳路徑，并反饋給道路上的車輛進行及時的調節。

（4）重復步驟（3）的操作，直到車輛到達目的地。

這種算法將路網信息進行了分區劃分，并且只選取一定范圍內的道路信息，這樣就使的在計算過程中所要計算的數據量大大減少，調高了算法的效率。并且在該算法中是按照車輛實時前進方向的道路位置進行道路數據的選取，避免了對已通過路段信息的重復計算。Dijkstra算法的路徑搜索范圍可以看成是以起點和目的地之間距離為半徑的圓形區域，而改進后的算法則可以看成是以起點和目的地為頂點的橢圓形區域如圖1所示，由圖可以很直觀的看出改進后的算法要明顯比原Dijkstra算法的數據搜索和處理量少很多。

圖1 Dijkstra算法與改進算法搜索范圍對比

3 小結

本文針對城市救援中的最短路徑Dijkstra算法進行了分析，針對其弊端采用動態最短路徑搜索的方法進行了改進，當然這種算法求得的最終路徑長度并不是最短的，但它以道路通行時間最短為標準，是符合城市應急救援車輛要求的一種算法，這對救援最佳路線的選擇具有重要的現實意義和應用價值。

參考文獻

[1]劉根生，蘇飛，趙娣.基于Dijkstra算法的兩點間多目標最優路徑問題建模和優化[J].池州師專學報.2007.21（3）：17-22.

[2]周玉清，張紅梅.多源最短路徑Floyd算法的分析與實現[C].第四屆海峽兩岸GIS發展研討會暨中國GIS協會第十屆年會，云南，2006.

作者簡介：

王廷（1985.6--）男，漢族，山東泰安人，助教，碩士，主要從事工程測量教育教學研究。