最短路径算法加速技术研究综述  

Survey of Speedup Techniques for Shortest Path Algorithms

作　　者：宋青[1] 汪小帆[1] 

机构地区：[1]上海交通大学电子信息与电气工作学院,上海闵行区200240

出　　处：《电子科技大学学报》2012年第2期176-184,共9页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(61074125);国家973计划(2010CB731400)

摘　　要：最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术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.

关 键 词：启发式 分层 大规模网络 最优化 最短路径 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] U491[自动化与计算机技术—计算机科学与技术]