An Optimal Path Algorithm Based on Hierarchically Structured Topographical Network
Cao Guo-feng · 2006
The classic Dijkstra algorithm is based on the planar topographical network,the expanding time for searching Optimal Path will increase sharply when the number of network nodes enlarges. In this paper,a path algorithm,namely bidirectional hierarchical wayfinding algorithm(BHWA )which is based on hierarchically structured topographical network(HiTopo) has been developed to speed up searching path. BHWA has two novel features which distinguish itself from existing method. Firstly,structure HiTopo is based on local connectivity of the classified network other than spatial distance. Secondly,it searches arc from two directions which improves upon search node along one direction. An experimental work has been done with BHWA using the map of Beijing,which shown BHWA speeds up computation efficiently while keeps up low error. By farther research,another fact is noted. If the algorithm is optimized by heuristic search,its search speed can be accelerated three times at least.