《改進的Dijkstra最短路徑算法及其套用研究》是王樹西、吳政學撰寫的一篇論文。
基本介紹
- 中文名：改進的Dijkstra最短路徑算法及其套用研究
- 作者：王樹西、吳政學
- 論文來源：計算機科學
- 發表時間：2012
- 分類號：TP301.6
論文摘要,引文格式,
論文摘要
求最短路徑是一個套用很廣泛的問題。求最短路徑的算法有很多,公認較好的算法是Dijkstra標號法。但實驗結果表明,Dijkstra標號法有需要改進的地方:①其退出機制對不聯通的有向圖是無效的,會陷入死循環;②沒有涉及最短路徑上頂點的鄰接點(特指前面的相鄰點)問題;③沒有涉及多個頂點同時獲得p標號的問題。針對上述問題,對標號法進行了改進。算法實驗表明,改進的標號法能夠有效解決上述問題。在上述工作的基礎上,開發了"北京市道路最優路線選擇系統",以提供起點和終點之間的最優路線,幫助用戶選擇出行路線,使市民能夠避過交通最擁堵的路段,節約出行時間。
引文格式
王樹西,吳政學.改進的Dijkstra最短路徑算法及其套用研究[J].計算機科學,2012,39(05):223-228.
