改进的Dijkstra最短路径算法及其应用研究

摘要

求最短路径是一个应用很广泛的问题.求最短路径的算法有很多,公认较好的算法是Dijkstra标号法.但实验结果表明,Dijkstra标号法有需要改进的地方:①其退出机制对不联通的有向图是无效的,会陷入死循环；②没有涉及最短路径上顶点的邻接点(特指前面的相邻点)问题；③没有涉及多个顶点同时获得p标号的问题.针对上述问题,对标号法进行了改进.算法实验表明,改进的标号法能够有效解决上述问题.在上述工作的基础上,开发了“北京市道路最优路线选择系统”,以提供起点和终点之间的最优路线,帮助用户选择出行路线,使市民能够避过交通最拥堵的路段,节约出行时间.%The problem of " the shortest path" has wide application. There are many algorithms to solve this problem and the best one is "Dijkstra's label algorithm". But experiment results show that this algorithm needs to be improved: Qthe algorithm's exit mechanism is ineffective to non-unicom figure and will fall into an infinite loop:(2)The algorithm is not concerned in the problem of previous adjacent vertices in shortest path: (3)The algorithm is not concerned in the problem that more vertices obtain the "p-label" at the same time. This paper improved the "Dijkstra's label algorithm". Experiment results indicate that the improved algorithm can solve above problems effectively. On the basis of the above work, we developed the "Beijing Road optimal route selection system", which help users to select the shorted route,so that people can avoid the most congested road traffic and save time.