摘要： Dijkstra算法在求解震后交通网络的最优路径时没有考虑抢修时间。为此，提出一种改进的Dijkstra算法。考虑抢修时间的影响因素，在抢修时间没到时，对应边不连通，此时到达该边的一个顶点，若想通过该边，则必须等待直到该边连通为止，采用数学归纳法证明改进算法所求的路径即最短路径。实验结果表明，与Dijkstra算法相比，该算法求解最优路径耗时更少。

关键词: 地震, 交通网络, 最优路径, Dijkstra算法

Abstract: 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.

Key words: earthquake, traffic network, optimum path, Dijkstra algorithm

中图分类号: 

• TP399