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

摘要：

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

关键词：最短路径、Dijkstra标号法、城市交通、最优路线选择

所属期刊栏目：39

分类号：TP392(计算技术、计算机技术)

资助基金：“对外经济贸易大学学术创新团队项目”和“对外经济贸易大学‘211工程'三期建设项目”资助

在线出版日期：2012-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：223-228