A circuitous shortest path algorithm labeled by previous-arc vector group in navigation GIS
Lin Yang, Shunping Zhou, Bo Wan, Xiaofang Pan · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2008
Path planning, as the core module of navigation GIS, its efficiency and accuracy has a crucial impact on the navigation system. General shortest-path algorithm is based on the classic node label-setting algorithm, which does not consider the situation of including circuitous road sections. Therefore, sometimes it will neglect the closer circuitous path at hand but find the farther path or even failed to find any path in the real road network with complicated traffic restrictions. For the sake of finding more accurate path, this paper presents a circuitous shortest path algorithm labeled by previous-arc vector group. Firstly, we generate incremental network topological relationships according to two random positions travelers are interested in. Secondly, we construct a vector group including previous arc, and seek the way by labeling the previous-arc vector group. Finally, the shortest path in the sense of mathematics which may contain circuitous road sections can be acquired. An experimental work has been done with this algorithm using the map of Beijing, which showed that the algorithm not only well improved the accuracy of the shortest path result between the two random positions in the road network, but also kept the efficiency of the classic node labeled algorithm.