基于预处理的点到点最短路径计算方法  

An algorithm for point to point shortest paths based on preprocessing

作　　者：陆文琦 谷远利[1] 李萌 王硕 张源 LU Wen-qi;GU Yuan-li;LI Meng;WANG Shuo;ZHANG Yuan(MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China)

机构地区：[1]北京交通大学城市交通复杂系统理论与技术教育部重点实验室,北京100044

出　　处：《山东科学》2018年第2期64-71,共8页Shandong Science

基　　金：国家重点基础研究发展计划(973计划)(2012CB725403);北京市科技计划项目(Z121100000312101)

摘　　要：基于经典的Dijkstra算法,研究采用预处理的点到点最短路径算法。通过引入双向Dijkstra和基于reach的预处理方法形成新的RE算法,并利用C++编程设计算法程序,将新算法应用于交通工程领域。利用EFSS数据结构搭建考虑交叉口和路段延误的交通网络,检验新算法的适用性和效率,结果发现RE算法与Dijkstra算法相比,搜索速度有大幅提升且能保证路径查询的正确性,RE算法在大规模网络上优势更为显著,查询时间约为Dijkstra算法的10%。Based on the classical Dijkstra algorithm,an algorithm for point to point shortest paths based on preprocessing was studied.The bidirectional Dijkstra algorithm and the reach-based preprocessing method were introduced to establish the new RE algorithm in this paper.The program of the new algorithm was compiled with C＋＋ and the new algorithm was applied to traffic engineering field.Traffic networks considering delay on roads and intersections were constructed by using EFSS data structure to test the applicability and efficiency of RE algorithm.The results reveal that compared with the original Dijkstra algorithm,the RE algorithm has a significant increase in the search speed and can ensure the correctness of path query.On large-scale networks,the new RE algorithm shows great advantages and its query time is approximately 10% of the Dijkstra algorithm.

关 键 词：双向 DIJKSTRA 算法 基于 REACH 的剪枝方法 RE算法 路径优化 

分 类 号：U116.2[交通运输工程]