A Circuitous shortest path algorithm labeled by previous-arc vector group in navigation GIS
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.
Previous-arc vector group label-setting circuitous path shortest path road network
Lin Yang Shunping Zhou Bo Wan Xiaofang Pan
Faculty of Information Engineering,China University of Geoscience(Wuhan),388 Lumo Road,Wuhan,China 4 Faculty of Information Engineering,China University of Geoscience(Wuhan),388 Lumo Road,Wuhan,China 4 School of Urban and Environment Science,Xinyang Normal University,237 Changan Road,Xinyang,Henan 46
国际会议
第16届国际地理信息科学与技术大会(16th International Conference on GeoInformatics and the Joint Conference)
广州
英文
2008-06-28（万方平台首次上网日期，不代表论文的发表时间）