A Fast Algorithm for Calculating APSP by Paths Block

doi:10.3969/j.issn.1006-2475.2017.12.002

Abstract

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

CLC Number:

TP393

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.

References

［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]	ZHANG Xiao-fang, FENG Hui-fang. Dynamic Optimal Path Planning Based on Trajectory Big Data [J]. Computer and Modernization, 2021, 0(11): 82-88.
[2]	LI Wei-dong, XU Shu-kun, WANG Yun-ming. Analysis of New York Rail Transit Network Characteristics Based on Complex Network [J]. Computer and Modernization, 2021, 0(02): 94-99.
[3]	WANG Hai-hong, LIU Li. Improved Path Search Algorithm Based on Layering and Reinforcement Learning [J]. Computer and Modernization, 2020, 0(11): 77-82.
[4]	XU Xiao-yuan, LI Hai-bo, YU Ben-cheng, LIU Fang. Semi-supervised Overlapping Community Finding with Pairwise Constraints [J]. Computer and Modernization, 2020, 0(08): 63-68.
[5]	CHEN Jing-yi, XU Ming-hai, YANG Xi, DU Fan. An Improved HK Social Network Modeling Method [J]. Computer and Modernization, 2019, 0(02): 123-.
[6]	MA Jia-yan, WANG Ping,XIA Wei, SHEN Hong-wei. Research on Network Traffic Prediction and Early Warning in Complex Networks [J]. Computer and Modernization, 2018, 0(01): 102-106.
[7]	WEN Zhen-qian, LIN You-fang, WU Zhi-hao. Analysis on Driving Force of Dishes Based on Complex Data Network in Catering Field [J]. Computer and Modernization, 2017, 0(7): 1-9.
[8]	CHEN Gao, WU Guang-chao. Information Propagation Model in Online Social Network Based on PageRank [J]. Computer and Modernization, 2017, 0(1): 101-105.
[9]	LI Meng1,2, MA Yi-fang3, JIANG Xin1,2, MA Li-li4, ZHENG Zhi-ming1,2. Competition Dynamics of Information Propagation on Complex Network [J]. Computer and Modernization, 2016, 0(1): 104-107.
[10]	WANG Zhu. A New Social Network Modeling Method [J]. Computer and Modernization, 2015, 0(12): 57-.
[11]	FAN Chao1, WANG Zhong-xi2, GAO Lu-bin3. Visibility Network Analysis on Official Documents Distribution Records [J]. Computer and Modernization, 2014, 0(5): 150-155.
[12]	GAO Hongwei1, XU Yong2. Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes [J]. Computer and Modernization, 2014, 0(4): 109-112.
[13]	JIA Sui-min, HU Ming-sheng, JIA Zhi-juan. Spatio-temporal Trend and Seismic Anomaly of Historical Earthquake Based on Complex Network [J]. Computer and Modernization, 2014, 0(12): 1-5.