| 适用于大规模网络的全源最短路径重优化算法——RASP算法 |
| |
| 引用本文： | 江锦成,吴立新,张媛媛,刘善军.适用于大规模网络的全源最短路径重优化算法——RASP算法[J].东北大学学报(自然科学版),2017,38(7):1037-1042. |
| |
| 作者姓名： | 江锦成 吴立新 张媛媛 刘善军 |
| |
| 作者单位： | (1. 北京师范大学 减灾与应急管理研究院， 北京100875; 2. 东北大学 资源与土木工程学院， 辽宁 沈阳110819; 3. 中南大学 地球科学与信息物理学院， 湖南 长沙410083; 4. 中国矿业大学(北京) 地球科学与测绘工程学院， 北京100083) |
| |
| 基金项目： | 国家高技术研究发展计划项目(2011AA120302). |
| |
| 摘 要： | 为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.
|
| 关 键 词： | 重优化 全源 最短路径 大规模网络 Floyd算法 Dijkstra算法 |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《东北大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《东北大学学报(自然科学版)》下载免费的PDF全文 |
