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

• 作者: 李洪波 王茂波
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: Floyd最短路径 AV集合 可达表A 可发表B 仅一次插入矩阵M
• 年，卷（期）: 2006,（34）
• 所属期刊栏目: 学术探讨
• 页码范围: 60-63
• 页数: 4页
• 分类号: TP331
• 字数: 4509字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.34.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李洪波	烟台师范学院数学与信息学院	14	130	6.0	11.0
2	王茂波	大连理工大学计算机系	1	64	1.0	1.0