中文摘要：

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

英文摘要：

The time complexity of traditional Dijkstra algorithm is quadratic times of the number of road net nodes, which results in its low efficiency for path planning. Existing improved Dijkstra algorithms are orientated to static road net nodes and thus influence their path planning speeds. This paper presented a dynamic road network nodes based Dijkstra algorithm. The road net was simplified by screening out the comer nodes, cross nodes, T cross nodes as well as those nodes that more than four paths going through of them. Such nodes of other types were abandoned. The number of road nodes of the optimized road net was decreased which is helpful to improve the path planning speed. Experiment results indicate that target nodes of a road net can be added and removed during the path planning process. When planning the same road net, the time consumption of traditional Dijkstra algorithm increases with the number of the task nodes, while that of the proposed Dijkstra algorithm stays the same even though the number of task nodes is sharply increased. The feasibility and effectiveness of the proposed Dijkstra algorithm was validated.