Research on Dynamic Road Net Nodes Based Dijkstra Algorithm for Path Planning
Lie Guo, Shujun Sun, Zejian Ren, Bing Li · 2013
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 corner 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.