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

摘要

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