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

Improved Dijkstra Algorithm for Solving Optimum Path After Earthquake

作　　者：李敬贤[1] 厉小润[1] 

机构地区：[1]浙江大学电气工程学院,杭州310027

出　　处：《计算机工程》2012年第6期271-272,275,共3页Computer Engineering

基　　金：浙江省重大科技专项重点工业基金资助项目(2010C11069)

摘　　要：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.

关 键 词：地震 交通网络 最优路径 DIJKSTRA算法 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]