图的最优矩阵构建研究

摘要：

为了提高图的最优矩阵的构建效率,文中通过对Floyd算法的研究,进一步提出了对其进行四层优化的方法,通过对图的矩阵中的特殊元素的删除和在计算前的判断减少了不必要的计算,加入贪心算法使其减少中间结果的生成,使中间结果更加接近图的最优矩阵.优化后的Floyd算法在很大程度上提高了执行效率,使其在实际应用中更加可取,经过逐步的优化使改进后的算法在运行时间上平均时间最多减少为原来的四分之一,而且随着图顶点数目的增加,修改后的Floyd算法效率有显著的提高,因此,在实际应用中是一个切实可行的算法.

关键词：最短路径、Floyd算法、贪心算法、最优矩阵

所属期刊栏目：23

分类号：TP301.6(计算技术、计算机技术)

资助基金：新疆自治区科技计划项目200732143

在线出版日期：2013-10-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：151-154,175