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

发布时间：2018-10-11 06:55

【摘要】：为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.
[Abstract]:In order to improve the efficiency of solving the all-source shortest path in large-scale networks, a fast and accurate all-source shortest path solution method, RASP (reoptimization-based all-pairs shortest path) algorithm), is proposed based on the theory of re-optimization. This paper analyzes the correlation and difference between the shortest path trees of different sources, and realizes the efficient conversion between the shortest path trees of different sources based on the theory of reoptimization on the basis of the known tree of the shortest path of single source. Then the RASP algorithm for solving all the shortest paths efficiently is obtained, and the time complexity of RASP algorithm is proved to be O (3n~2 2nm). The experimental results show that the RASP algorithm can outperform the Floyd algorithm, the n-order Dijkstra algorithm and its improved algorithm effectively in both sparse and dense networks.
【作者单位】： 北京师范大学减灾与应急管理研究院;东北大学资源与土木工程学院;中南大学地球科学与信息物理学院;中国矿业大学(北京)地球科学与测绘工程学院;
【基金】：国家高技术研究发展计划项目(2011AA120302)
【分类号】：TP301.6

【参考文献】

相关期刊论文 前6条

1 李鸣鹏;邹兆年;高宏;赵正理;;不确定图上期望最短距离的计算[J];计算机研究与发展;2012年10期

2 邢星星;赵国兴;骆祖莹;方浩;;基于GPU的全源最短路径算法[J];计算机科学;2012年03期

3 陆锋;最短路径算法:分类体系与研究进展[J];测绘学报;2001年03期

4 吴京,景宁,陈宏盛;最佳路径的层次编码及查询算法[J];计算机学报;2000年02期

5 严寒冰,刘迎春;基于GIS的城市道路网最短路径算法探讨[J];计算机学报;2000年02期

6 徐业昌,李树祥,朱建民,许岚,曹次华;基于地理信息系统的最短路径搜索算法[J];中国图象图形学报;1998年01期

【共引文献】

相关期刊论文 前10条

1 杨佳荣;齐倩倩;李海军;;旅游服务信息系统的分析与设计[J];电子商务;2017年07期

2 江锦成;吴立新;张媛媛;刘善军;;适用于大规模网络的全源最短路径重优化算法——RASP算法[J];东北大学学报(自然科学版);2017年07期

3 冯景泽;颜何生;;弯曲走廊最短路径算法及在水能计算中的应用[J];人民珠江;2017年06期

4 张翰林;关爱薇;傅珂;孙廷凯;;Dijkstra最短路径算法的堆优化实验研究[J];软件;2017年05期

5 夏帅;王华秀;于幸;徐宇嘉;;基于GPS定位技术的旅游导航系统的研究[J];电脑知识与技术;2017年09期

6 邱儒琼;聂小波;王海侠;;基于WiFi的室内位置服务路径规划研究[J];地理空间信息;2017年04期

7 康文雄;许耀钊;;节点约束型最短路径的分层Dijkstra算法[J];华南理工大学学报(自然科学版);2017年01期

8 许自昌;;基于最小生成树的渠道系统优化布局模型[J];农业工程学报;2017年01期

9 王艳;黄开建;孙茂圣;李开荣;朱俊武;;面向智能导览的个性化线路规划研究[J];现代电子技术;2016年20期

10 徐小奇;;基于海量出租车轨迹数据的智能推荐系统研究[J];电子制作;2016年18期

【二级参考文献】

相关期刊论文 前3条

1 卢风顺;宋君强;银福康;张理论;;CPU/GPU协同并行计算研究综述[J];计算机科学;2011年03期

2 袁野;王国仁;;面向不确定图的概率可达查询[J];计算机学报;2010年08期

3 周益民,孙世新,田玲;一种实用的所有点对之间最短路径并行算法[J];计算机应用;2005年12期

【相似文献】

相关期刊论文 前10条

1 孟祥清;长度递增法求最短路径[J];河北能源职业技术学院学报;2002年04期

2 傅清祥,王朝利,孙剑峰;长廊最短路径的最优算法[J];计算机辅助设计与图形学学报;2002年12期

3 王涛,李伟生;最短路径子图[J];北方交通大学学报;2004年02期

4 徐凤生;最短路径的求解算法[J];计算机应用;2004年05期

5 王涛,李伟生;低代价最短路径树的快速算法[J];软件学报;2004年05期

6 宣士斌;基于分流算法的最短路径求解算法[J];计算机工程与应用;2004年20期

7 徐凤生;李天志;;所有最短路径的求解算法[J];计算机工程与科学;2006年12期

8 白青海;;一种求解交通图最短路径的方案[J];内蒙古民族大学学报(自然科学版);2007年02期

9 章昭辉;;一种基于离散变权网络的动态最短路径快速算法[J];计算机科学;2010年04期

10 原慧琳;汪定伟;;最短路径的可达矩阵算法[J];信息与控制;2011年02期

相关会议论文 前10条

1 温粉莲;唐常杰;乔少杰;许刚;刘威;左R，

本文编号：2263270