基于动态路网节点的Dijkstra算法路径规划研究

• 作者: 任泽建 孙淑军 李兵 郭烈
• 来源期刊: 控制工程期刊：中英文版
• 学科: 工学
• 关键词: 路径规划 DIJKSTRA算法 动态路网节点 最短路径
• 年，卷（期）: 2013,（6）
• 页码范围: 359-366
• 页数: 8页
• 分类号: TP242

摘要

传统Dijkstra算法随着路网节点数目的增多，其时间复杂度成节点数目平方级增加，现有的Dijkstra改进算法无法动态改变原路网节点数目从而影响算法的计算效率。本文提出一种能够动态增加和删除路网节点的Dijkstra算法，提取原始路网模型中的边界角点、十字交叉节点、T型交叉节点以及有其他四条以上路段通过的节点，剔除这些节点之间构成的路段上的其他任务点得到一个新的优化路网模型，保留有原始路网模型的骨架结构的同时简化了路网结构，从而使时间复杂度降低，提高其运行效率。仿真表明，改进算法能够实现动态增删路网节点，在同一路网环境中，随着路网节点数目增多，传统算法耗时越来越大，而改进算法基本维持不变，验证了改进算法的可行性和有效性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭烈	大连理工大学汽车工程学院	39	308	10.0	16.0
2	李兵	大连理工大学汽车工程学院	10	315	6.0	10.0
3	任泽建	大连理工大学汽车工程学院	3	4	1.0	2.0
4	孙淑军	大连理工大学汽车工程学院	1	0	0.0	0.0