Floyd最短路径算法的动态优化

被引：30

作者：

李洪波 ^{[1
]}

王茂波 ^{[2
]}

机构：

[1] 烟台师范学院数学与信息学院

[2] 大连理工大学计算机系

来源：

计算机工程与应用 | 2006年 / 34期

关键词：

Floyd最短路径; AV集合; 可达表A; 可发表B; 仅一次插入矩阵M;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

根据Floyd最短路径算法的三层循环,设计了动态优化新算法。动态优化新算法设计了独特的动态AV集合、可发表B和可达表A,分别对原算法的外层循环、中层循环和内层循环进行极小化的运算。在极小化的处理过程中,为保证可发表B和可达表A中不存在重复元素,引入了仅一次插入矩阵M。动态优化新算法的时间复杂度为O(n2+｜AV｜×e2/n2)(｜AV｜!n),使得算法能够根据点数、边数和边的实际分布动态调整自身的性能。

引用

页码：60 / 63

页数：4

共 12 条

[1] 最短路径的求解算法 [J].