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

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