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

摘要：

为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.

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

所属期刊栏目：38

分类号：TP301.6(计算技术、计算机技术)

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

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

页数：共6页

页码：1037-1042