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

求最短路径是一个应用很广泛的问题求最短路径的算法有很多，公认较好的算法是dijkstra标号法。但实验结果表明，dijkstra标号法有需要改进的地方:①其退出机制对不联通的有向图是无效的，会陷入死循环;②没有涉及最短路径上顶点的部接点(特指前面的相部点)问题;③没有涉及多个顶点同时获得p标号的问题。针对上述问题，对标号法进行了改进。算法实验表明，改进的标号法能够有效解决上述问题。在上述工作的基础上，开发了“北京市道路最优路线选择系统”，以提供起点和终点之间的最优路线，帮助用户选择出行路线，使市民能够避过交通最拥堵的路段，节约出行时间。