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

摘要：

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

关键词：最优路径算法、层次网络拓扑结构、双向路径搜索

所属期刊栏目：11

分类号：P208(一般性问题)

在线出版日期：2006-08-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1004-1009