摘要
在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.
出处
《科学技术与工程》
2011年第28期6875-6878,6892,共5页
Science Technology and Engineering
基金
国家自然科学基金资助项目(79930400)资助
