求解震后最优路径的改进Dijkstra算法

英文篇名：Improved Dijkstra Algorithm for Solving Optimum Path After Earthquake
中文刊名：计算机工程
英文刊名：Computer Engineering
作者：李敬贤 ; 厉小润
英文作者：LI Jing-xian ; LI Xiao-run(College of Electrical Engineering ; Zhejiang University ; Hangzhou 310027 ; China)
中文关键词：地震 ; 交通网络 ; 最优路径 ; Dijkstra算法
英文关键词：earthquake ; traffic network ; optimum path ; Dijkstra algorithm
出版日期：2012-03-20
机构：浙江大学电气工程学院;
年：2012
期：06
出版单位：计算机工程

摘要

Dijkstra算法在求解震后交通网络的最优路径时没有考虑抢修时间。为此,提出一种改进的Dijkstra算法。考虑抢修时间的影响因素,在抢修时间没到时,对应边不连通,此时到达该边的一个顶点,若想通过该边,则必须等待直到该边连通为止,采用数学归纳法证明改进算法所求的路径即最短路径。实验结果表明,与Dijkstra算法相比,该算法求解最优路径耗时更少。
Because the repair time is not taken into account,Dijkstra algorithm can not find the optimum path in a traffic network after earthquake.To solve the problem above,an improved Dijkstra algorithm with repair time is proposed in this paper.It considers the influence factors of repair time.The side is not connected until it is repaired.In order to pass the side,waiting for it to be connected is needed.According to this idea,the Dijkstra algorithm is improved.It uses mathematical induction to prove the desired path of the improved algorithm is the shortest path.Experimental result shows that the time of this algorithm to find the optimum path is less than Dijkstra algorithm.

引文

[1]Kenneth H R.Discrete Mathematics and Its Applications[M].北京:机械工业出版社,2003.
    [2]姚清林.优选地震救灾路径的图与模糊集算法[J].自然灾害学报,2006,15(2):143-148.
    [3]袁正午,武志涛,杨富平.基于抢修时间的震后最优路径选择算法及GIS实现[J].计算机应用,2010,30(7):1909-1912.
    [4]Dijkstra E W.A Note on Two Problems in Connection withGraphs[EB/OL].(2010-11-21).http://d.wanfangdata.com.cn/NSTLQK_10.1007-BF01386390.aspx.