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

• 作者: 张源 李萌 王硕 谷远利 陆文琦
• 来源期刊: 山东科学
• 学科: 交通运输
• 关键词: 双向Dijkstra算法 基于reach的剪枝方法 RE算法 路径优化
• 年，卷（期）: 2018,（2）
• 所属期刊栏目: 交通运输
• 页码范围: 64-71
• 页数: 8页
• 分类号: U116.2
• 字数: 4003字
• 语种: 中文
• DOI: 10.3976/j.issn.1002-4026.2018.02.011

摘要

基于经典的Dijkstra算法,研究采用预处理的点到点最短路径算法.通过引入双向Dijkstra和基于reach的预处理方法形成新的RE算法,并利用C++编程设计算法程序,将新算法应用于交通工程领域.利用EFSS数据结构搭建考虑交叉口和路段延误的交通网络,检验新算法的适用性和效率,结果发现RE算法与Dijkstra算法相比,搜索速度有大幅提升且能保证路径查询的正确性,RE算法在大规模网络上优势更为显著,查询时间约为Dijkstra算法的10％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李萌	北京交通大学城市交通复杂系统理论与技术教育部重点实验室	12	72	3.0	8.0
2	王硕	北京交通大学城市交通复杂系统理论与技术教育部重点实验室	13	51	4.0	6.0
3	谷远利	北京交通大学城市交通复杂系统理论与技术教育部重点实验室	18	61	4.0	6.0
4	陆文琦	北京交通大学城市交通复杂系统理论与技术教育部重点实验室	7	16	2.0	3.0
5	张源	北京交通大学城市交通复杂系统理论与技术教育部重点实验室	5	23	2.0	4.0