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

Improved Floyd Algorithm for Shortest-path Problem in Network Optimization

作　　者：邹桂芳[1] 张培爱[1] 

机构地区：[1]暨南大学信息科学技术学院数学系,广州510632

出　　处：《科学技术与工程》2011年第28期6875-6878,6892,共5页Science Technology and Engineering

基　　金：国家自然科学基金资助项目(79930400)资助

摘　　要：在Gauss-Seidel迭代法思想的基础上,提出了一种改进的Floyd算法来计算任意两点之间的最短路问题。通过对带权邻接矩阵按照行列由小到大和由大到小的顺序进行计算,只需两步迭代求得最短路长。算法分析和计算实例表明,改进的Floyd算法大大减少了迭代次数,提高了算法效率。An improved Floyd algorithm for all-pairs shortest path problems is proposed, based on Gauss-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 itera- tions and＂ efficiency.

关 键 词：最短路问题 FLOYD算法 Gauss—Seidel迭代法 算法改进 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]