文献类型：期刊文章

作　　者：王树西[1] 吴政学[1]

机构地区：[1]对外经济贸易大学信息学院,北京100029

出　　处：《计算机科学》

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

年　　份：2012

卷　　号：39

期　　号：5

起止页码：223-228

语　　种：中文

收录情况：BDHX、BDHX2011、CSA、CSCD、CSCD2011_2012、IC、JST、RCCSE、UPD、ZGKJHX、核心刊

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

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

分 类 号：TP392]