Accelerated and optimized method of Floyd algorithm to find out shortest path

doi:10.3778/j.issn.1002-8331.2009.17.012

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (17): 41-43.DOI: 10.3778/j.issn.1002-8331.2009.17.012

• 研究、探讨 • Previous Articles Next Articles

Accelerated and optimized method of Floyd algorithm to find out shortest path

ZHANG De-quan,WU Guo-lin,LIU Deng-feng

Department of Computer，Guilin College of Aerospace Technology，Guilin，Guangxi 541004，China

Received:2009-02-03 Revised:2009-03-27 Online:2009-06-11 Published:2009-06-11
Contact: ZHANG De-quan

最短路问题的Floyd加速算法与优化

张德全,吴果林,刘登峰

桂林航天工业高等专科学校计算机系，广西桂林 541004

通讯作者: 张德全

Abstract

Abstract: Floyd algorithm is the most efficient method to find out the shortest path between any two nodes in the network.This paper illustrates the acceleration and optimization of Floyd algorithm in the network without negative circuit，and establishes serial number matrix to find out the shortest path.The algorithmic analysis and calculation examples show that the amount of calculation reduces greatly after using the accelerated and optimized method of Floyd algorithm and it is simple，intuitive and optimize to find out the path.

Key words: shortest path, Floyd algorithm, accelerated method, path

摘要： Floyd算法是求解网络中任意两点之间最短路的高效算法，文章给出了在不含负回路的网络中Floyd加速算法及优化方法，并构造了求解最短路径的序号矩阵。算法分析和计算实例表明，优化后的Floyd加速算法迭代速度快，计算量大大减少，路径寻找简单、直观。

关键词: 最短路, Floyd 算法, 加速方法, 最短路径

ZHANG De-quan,WU Guo-lin,LIU Deng-feng. Accelerated and optimized method of Floyd algorithm to find out shortest path[J]. Computer Engineering and Applications, 2009, 45(17): 41-43.

张德全,吴果林,刘登峰. 最短路问题的Floyd加速算法与优化[J]. 计算机工程与应用, 2009, 45(17): 41-43.

[1]	KONG Jili, ZHANG Pengkun, LIU Xiaoping. Research on Improved A* Algorithm of Bidirectional Search Mechanism [J]. Computer Engineering and Applications, 2021, 57(8): 231-237.
[2]	HUAI Chuangfeng, GUO Long, JIA Xueyan, ZHANG Zihao. Improved A* Algorithm and Dynamic Window Method for Robot Dynamic Path Planning [J]. Computer Engineering and Applications, 2021, 57(8): 244-248.
[3]	LI Jun. Improved Social Force Crowd Evacuation Simulation Model Combined with Shortest Path [J]. Computer Engineering and Applications, 2021, 57(8): 264-270.
[4]	LIAO Liefa, LI Haohan, LI Shuai, ZHU Helong, LI Zhijun. Research on Control Strategy of Soccer Robot Combined with Winner-Take-All [J]. Computer Engineering and Applications, 2021, 57(7): 136-143.
[5]	ZHANG Dieyi, YIN Lijie. Clustering-Preserving Representation Learning on Heterogeneous Network [J]. Computer Engineering and Applications, 2021, 57(7): 144-150.
[6]	HAN Xiaowei, HAN Zhen, YUE Gaofeng, CUI Jianjiang. Path Planning Algorithm of Disaster Relief UAV Based on Optimized A [J]. Computer Engineering and Applications, 2021, 57(6): 232-238.
[7]	ZHU Jiaying, GAO Maoting. AUV Path Planning Based on Particle Swarm Optimization and Improved Ant Colony Optimization [J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
[8]	LIU Jianyu, FAN Pingqing. Path Planning of Manipulator Based on Improved RRT*-connect Algorithm [J]. Computer Engineering and Applications, 2021, 57(6): 274-278.
[9]	HU Wei’an, ZOU Junzhong, GUO Yucheng, ZHANG Jian, WANG Bei. Lesion Recognition Method of Pathological Images Based on Multidimensional Features [J]. Computer Engineering and Applications, 2021, 57(6): 144-151.
[10]	WANG Di, LI Caihong, GUO Na, LIU Guoming, GAO Tengteng. Local Path Planning of Mobile Robot Based on Fuzzy Potential Field Method [J]. Computer Engineering and Applications, 2021, 57(6): 212-218.
[11]	JIANG Lin, FANG Dongjun, LEI Bin, LI Weigang. Research Status and Trend of Navigation Algorithm for Mobile Robot with Monocular Vision [J]. Computer Engineering and Applications, 2021, 57(5): 1-9.
[12]	MA Xianghua, ZHANG Qian. Research on Improved Ant Colony Algorithm in Robots Path Planning [J]. Computer Engineering and Applications, 2021, 57(5): 210-215.
[13]	LI Yuqi, LIU Zhiqian, CHENG Ningyi, WANG Yingying, ZHU Chunli. Path Planning of UAV Under Multi-constraint Conditions [J]. Computer Engineering and Applications, 2021, 57(4): 225-230.
[14]	REN Junxiao, CHANG Xin, HOU Ying, CAO Xiaobo. Shared Parking Allocation Model Based on Users’ Preferences and Revenue from Platform [J]. Computer Engineering and Applications, 2021, 57(24): 242-248.
[15]	WANG Jiayue, SHI Li. Research on Path Optimization and Charging Strategy of Electric Refrigerated Vehicle Considering Cost of Battery Capacity Degradation [J]. Computer Engineering and Applications, 2021, 57(24): 283-289.

Accelerated and optimized method of Floyd algorithm to find out shortest path

最短路问题的Floyd加速算法与优化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics