基于分层网络拓扑结构的最优路径算法

由于Dijkstra算法的基础是平面网络拓扑模型，因此当计算网络的节点数目较大时，计算的时间将急剧膨胀。为了快速地搜索到最优路径，基于分层网络拓扑结构（HiTopo），提出了双向分层搜索最优路径算法（BHWA）；该算法对现有分层路径算法进行了以下两点改进：（1）将分级网络的局部连通性作为划分子图的指标；（2）在路径计算过程中，使用弧段作为搜索目标，并采取了双向搜索策略。通过北京道路数据的实验表明：该算法在保持分层路径算法高效性的基础上，还提高了路径搜索结果的准确性；通过进一步研究表明，如果使用启发式搜索来对算法进行优化，则可以使算法的速度有更大的提升。

An Optimal Path Algorithm Based on Hierarchically Structured Topographical Network

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.