文献类型：期刊文章

作　　者：李洪波[1] 王茂波[2]

机构地区：[1]烟台师范学院数学与信息学院,山东烟台264025 [2]大连理工大学计算机系,辽宁大连116023

出　　处：《计算机工程与应用》

年　　份：2006

卷　　号：42

期　　号：34

起止页码：60-63

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

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

关 键 词：Floyd最短路径  AV集合  可迭表A  可发表B  仅一次插入矩阵M  

分 类 号：TP331]