在智能交通系统中的应用.PDF

第 9 期 王 峰等: Dijkstra 及基于 Dijkstra 的前 N 条最短路径算法在智能交通系统中的应用 2·03 · Dijkstra 及基于 Dijkstra 的前 N 条最短路径算法 在智能交通系统中的应用 * 1 1 1 2 1 王 峰 , 游志胜 , 曼丽春 , 高 燕 , 汤丽萍 ( 1. 四川大学 计算机学院, 四川 成都 610065; 2. 成都信息工程学院, 四川 成都 610225) 摘 要: 介绍了 Dijkstra 算法在智能交通系统的套牌车查询子系统中的应用 ; 分析指出了文献 [ 1] 中算法存在 的问题; 通过对此算法的改进, 完善了基于 Dijkstra 算法的前 N 条最短路径算法。通过实验及实际应用对改进后 的算法进行了验证。 关键词: Dijkstra 算法; 智能交通; 前 N 条最短路径 中图法分类号: TP301. 6 文献标识码: A 文章编号 : 1001- 3695( 2006) 09- 0203- 03 Application of Dijkstra and Dijkstra-based N-Shortest-Paths Algorithm to Intelligent Transportation Systems 1 1 1 2 1 WANG Feng , YOU Zhi-sheng , MAN Li-chun , GAO Yan , TANG Li-ping ( 1. College of Computer Science, Sichuan University, Chengdu Sichuan 610065 , China; 2 . Chengdu University of Information Technology, Chengdu Sichuan 610225, China) Abstract: Application of Dijkstra algorithm to intelligent transportation systems is presented. Problems of reference[ 1] are analyzed. Through improvement on the algorithm, the Dijkstra-based N-Shortest-Paths algorithm is consummated. The improved algorithm is proved to be correct and efficient by experiments and practical application. Key words: Dijkstra Algorithm; Intelligent Transportation Systems; N-Shortest-Paths 在智能交通系统的实践过程中, 发现套牌车( 一般指没有 例 1 车牌号为京 BF6446 在 2005 年 5 月 30 日那天, 于 办理入户手续, 盗用别的汽车车牌行驶的汽车) 现象越来越严 17 时 23 分 33 秒出现在白广路, 17 时 26 分 12 秒出现在北河 重, 给相关部门的车辆管理工作带来了诸多不便。由于车牌图 沿大街北口, 其所用时间为 2 分 39 秒, 而这两个地点间的最短 片数据量较大, 如果完全由人工来识别套牌车, 不仅工作量巨 路径为 8 734m, 则其平均时速为