摘要
最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术3个方面综述了该领域最新、最具代表性的一些算法,包括作者在网络分层模型的构造及其分层搜索算法设计方面的最新成果。最后展望了该领域的未来研究方向。
The problem of efficient path computation arises in many domains of practical importance.Classical algorithms failed to apply to large-scale networks due to their heavy computational complexity.This paper reviews some latest representative results classified according to the underlying speedup techniques,including basic speedup techniques like priority queues,goal-directed techniques,and hierarchical approaches.Moreover,the paper introduces the most recent achievement of the authors on network hierarchy construction and hierarchical algorithm design.Finally,some future directions are discussed.
出处
《电子科技大学学报》
EI
CAS
CSCD
北大核心
2012年第2期176-184,共9页
Journal of University of Electronic Science and Technology of China
基金
国家自然科学基金(61074125)
国家973计划(2010CB731400)
关键词
启发式
分层
大规模网络
最优化
最短路径
heuristics
hierarchical
large-scale networks
optimization
shortest paths
