适用于大规模网络的全源最短路径重优化算法——RASP算法  

A Reoptimization-Based All-Pairs Shortest Path Algorithm for Large-Scale Network——RASP Algorithm

作　　者：江锦成[1] 吴立新[2,3] 张媛媛[4] 刘善军[2] 

机构地区：[1]北京师范大学减灾与应急管理研究院,北京100875 [2]东北大学资源与土木工程学院,辽宁沈阳110819 [3]中南大学地球科学与信息物理学院,湖南长沙410083 [4]中国矿业大学(北京)地球科学与测绘工程学院,北京100083

出　　处：《东北大学学报（自然科学版）》2017年第7期1037-1042,共6页Journal of Northeastern University(Natural Science)

基　　金：国家高技术研究发展计划项目(2011AA120302)

摘　　要：为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n^2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.In order to improve the computational performance of searching all-pairs shortest paths in a large-scale network, an exact all-pairs shortest path method- RASP algorithm is proposed based on the reoptimization theory. First, the correlation and difference between the shortest path trees with different sources are analyzed. Second,the efficient conversion from a known single-source shortest path tree to another one with different source is achieved based on the reoptimization-based theory. Furthermore, the reoptimization-based all-pairs shortest path （RASP） algorithm utilizes this conversion method to calculate efficiently all-pairs shortest paths. At last,the time complexity of RASP algorithm is proved to be 0（3n2 ＋ 2 nm）. The experimental test demonstrates that RASP algorithm gains the advantage over Floyd,^-Dijkstra algorithms and their improved algorithms in both sparse and dense networks.

关 键 词：重优化 全源 最短路径 大规模网络 FLOYD算法 DIJKSTRA算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]