一种基于路径阻断的求解最短路径算法

doi:10.3969/j.issn.1006-2475.2017.12.002

计算机与现代化

一种基于路径阻断的求解最短路径算法

(北京化工大学信息科学与技术学院,北京100029)

收稿日期:2017-04-12 出版日期:2017-12-25 发布日期:2017-12-26
作者简介:林家祺(1992-),男,广西贵港人,北京化工大学信息科学与技术学院硕士研究生,研究方向:基于复杂网络的社会网络分析；卢罡(1981-),男,吉林人，讲师,博士,研究方向:基于复杂网络的社会网络分析,基于GPGPU的高性能计算; 许南山(1956-)，男，福建莆田人，副教授，学士，研究方向：计算机网络与MIS系统。
基金资助:
国家自然科学基金资助项目(61602026)

A Fast Algorithm for Calculating APSP by Paths Block

(College of Information Science & Technology, Beijing University of Chemical Technology, Beijing 100029, China)

Received:2017-04-12 Online:2017-12-25 Published:2017-12-26

摘要/Abstract

摘要： 全源最短路径的求解是计算机科学、交通工程、地理信息系统等学科中的一个研究热点。随着网络规模不断增大，求解全源最短路径的时间复杂度急剧上升，这制约了复杂网络相关研究与应用的快速发展，因此最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。本文在BFS的基础上,引入路径阻断策略，利用已求得的单源最短路径节点的结果，加速全源最短路径的求解。实验结果表明该方法对大规模网络全源最短路径实现了加速计算。

关键词: 复杂网络, 全源最短路径, 广度优先遍历, 路径阻断

Abstract: The problem of All Pairs of Shortest Paths (APSP) has been a hot topic in the fields of computer science, traffic engineering， geographic information system, and so on. With the increasing size of the network, the time complexity of calculating APSP is increasing rapidly. Therefore, the efficiency of APSP algorithm is a general concern and is urgent in practical application. Based on the BFS, this paper introduces the path blocking strategy, which uses the results obtained by solving Single Source Shortest Path (SSSP) to accelerate the process of APSP. The experimental results show that this method realizes the acceleration.

Key words: complex network, APSP, BFS, poths block

中图分类号:

TP393

林家祺,卢罡,许南山. 一种基于路径阻断的求解最短路径算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.12.002.

LIN Jia-qi, LU Gang, XU Nan-shan. A Fast Algorithm for Calculating APSP by Paths Block[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.12.002.

参考文献

［1］Dijkstra E W. A note on two problems in connexion with graphs［J］. Numerical Mathematics, 1959,1(1):269-271. ［2］Bellman R. On a routing problem［J］. Quarterly of Applied Mathematics, 1958,16(1):87-90. ［3］李平,李永树. 一种基于Dijkstra并行线程算法的研究与实现［J］. 测绘与空间地理信息, 2014(9):50-53. ［4］周益民,孙世新,田玲. 一种实用的所有点对之间最短路径并行算法［J］. 计算机应用, 2005,25(12):2921-2922. ［5］张文金,许爱军. 基于云计算的混合并行遗传算法求解最短路径［J］. 电子技术应用, 2015,41(3):123-125. ［6］刘欣,王非. 两种GPU上改进的最短路径算法［J］. 计算机应用研究, 2014,31(5):1407-1409. ［7］李寅,邓仰东. 基于GPU的混合式全源对最短路径算法研究［J］. 微电子学与计算机, 2016(2):77-82. ［8］王一同. GPU加速技术在图论算法中的应用［D］. 成都:电子科技大学, 2014. ［9］Aridhi S, Lacomme P, Ren L, et al. A MapReduce-based approach for shortest path problem in large-scale networks［J］. Engineering Applications of Artificial Intelligence, 2015,41(C):151-165. ［10］Wei-Kleiner F. Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs［J］. Journal of Computer and System Sciences, 2016,82(1):23-44. ［11］Djidjev H, Chapuis G, Andonov R, et al. All-pairs shortest path algorithms for planar graph for GPU-accelerated clusters［J］. Journal of Parallel and Distributed Computing, 2015,85(C):91-103. ［12］Ortega-Arranz H, TorresY, Gonzalez-Escribano A, et al. Comprehensive evaluation of a new GPU-based approach to the shortest path problem［J］. International Journal of Parallel Programming, 2015,43(5):918-938. ［13］Davidson A, Baxter S, Garland M, et al.Work-efficient parallel GPU methods for single-source shortest paths［C］// 2014 28th IEEE International Parallel and Distributed Processing Symposium. 2014:349-359. ［14］Akiba T, Iwatat Y, Kawarabayashi K, et al. Fast shortest-path distance queries on road networks by pruned highway labeling［C］// Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX). 2014:147-154.

[1]	张小芳, 冯慧芳. 基于轨迹大数据的动态最优路径规划[J]. 计算机与现代化, 2021, 0(11): 82-88.
[2]	李卫东, 徐澍锟, 王运明. 基于复杂网络的纽约轨道交通网络特性分析[J]. 计算机与现代化, 2021, 0(02): 94-99.
[3]	王海红, 刘莉. 基于分层和强化学习的改进路径搜索算法[J]. 计算机与现代化, 2020, 0(11): 77-82.
[4]	许小媛, 李海波, 于本成, 刘芳. 具有对偶约束的半监督重叠社区发现方法[J]. 计算机与现代化, 2020, 0(08): 63-68.
[5]	陈婧怡，徐名海，杨溪，杜帆. 一种改进的HK社交网络建模方法[J]. 计算机与现代化, 2019, 0(02): 123-.
[6]	马佳艳，王萍，夏伟，申红伟. 复杂网络下的网络流量预测和预警研究[J]. 计算机与现代化, 2018, 0(01): 102-106.
[7]	温振前，林友芳，武志昊. 基于餐饮数据复杂网络的菜品拉动力分析[J]. 计算机与现代化, 2017, 0(7): 1-9.
[8]	陈皋，吴广潮. 基于PageRank的在线社交网络消息传播模型[J]. 计算机与现代化, 2017, 0(1): 101-105.
[9]	李甍1,2,马一方3,姜鑫1,2,马丽丽4,郑志明1,2. 一种复杂网络上信息传播的动态竞争机制[J]. 计算机与现代化, 2016, 0(1): 104-107.
[10]	王竹. 一种新型社交网络建模方法[J]. 计算机与现代化, 2015, 0(12): 57-.
[11]	樊超1，王重玺2，高鲁彬3. 政府公文收发记录的可视网络分析[J]. 计算机与现代化, 2014, 0(5): 150-155.
[12]	高洪伟1,徐勇2. 基于节点间的依赖程度划分网络中社团的算法[J]. 计算机与现代化, 2014, 0(4): 109-112.
[13]	贾遂民，胡明生，贾志娟. 基于复杂网络的历史地震时空分布及异常分析[J]. 计算机与现代化, 2014, 0(12): 1-5.

一种基于路径阻断的求解最短路径算法

A Fast Algorithm for Calculating APSP by Paths Block

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价