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   

  1. 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



  1. 桂林航天工业高等专科学校 计算机系,广西 桂林 541004
  • 通讯作者: 张德全

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 算法, 加速方法, 最短路径