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

江锦成¹，吴立新^2,3，张媛媛⁴，刘善军²

1. 北京师范大学减灾与应急管理研究院2. 东北大学资源与土木工程学院3. 中南大学地球科学与信息物理学院4. 中国矿业大学(北京)地球科学与测绘工程学院

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

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