网络优化中最短路问题的改进Floyd算法

摘要

在Gauss-Seidel迭代法思想的基础上,提出了一种改进的Floyd算法来计算任意两点之间的最短路问题.通过对带权邻接矩阵按照行列由小到大和由大到小的顺序进行计算,只需两步迭代求得最短路长.算法分析和计算实例表明,改进的Floyd算法大大减少了迭代次数,提高了算法效率.%An improved Floyd algorithm for all-pairs shortest path problems is proposed, based on Causs-Seidel iteration thought The shortest-path distance can be obtained quickly in two iterations, by calculating the weight adjacent matrix with row index and column index from small to large and from large to small at the same time. Algorithm analysis and calculation examples show that the improved Floyd algorithm is improved in the amount of iterations and'efficiency.