东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2017, Vol. 38 ›› Issue (7): 1037-1042.DOI: 10.12068/j.issn.1005-3026.2017.07.026

• 资源与土木工程 • 上一篇    下一篇

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

江锦成1， 吴立新2,3， 张媛媛4， 刘善军2   

  1. (1. 北京师范大学 减灾与应急管理研究院， 北京100875; 2. 东北大学 资源与土木工程学院， 辽宁 沈阳110819; 3. 中南大学 地球科学与信息物理学院， 湖南 长沙410083; 4. 中国矿业大学(北京) 地球科学与测绘工程学院， 北京100083)
  • 收稿日期:2016-04-29 修回日期:2016-04-29 出版日期:2017-07-15 发布日期:2017-07-07
  • 通讯作者: 江锦成
  • 作者简介:江锦成(1989-)，男，江西九江人，北京师范大学博士研究生； 吴立新(1966-)，男，江西宜春人，东北大学教授，博士生导师，教育部“长江学者奖励计划”特聘教授； 刘善军(1965-)，男，河北涿鹿人，东北大学教授，博士生导师.
  • 基金资助:
    国家高技术研究发展计划项目(2011AA120302).

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

JIANG Jin-cheng1， WU Li-xin2,3， ZHANG Yuan-yuan4， LIU Shan-jun2   

  1. 1. Academy of Disaster Reduction and Emergency Management， Beijing Normal University， Beijing 100875， China; 2. School of Resources & Civil Engineering， Northeastern University， Shenyang 110819， China; 3. School of Geoscience and Info-Physics， Central South University， Changsha 410083， China; 4. College of Geoscience and Surveying Engineering， China University of Mining & Technology， Beijing 100083， China.
  • Received:2016-04-29 Revised:2016-04-29 Online:2017-07-15 Published:2017-07-07
  • Contact: WU Li-xin
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

1112

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

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

Abstract: 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 O(3n2+2nm). The experimental test demonstrates that RASP algorithm gains the advantage over Floyd， n-Dijkstra algorithms and their improved algorithms in both sparse and dense networks.

Key words: reoptimization, all-pairs, shortest path, large-scale network, Floyd algorithm, Dijkstra algorithm

中图分类号: