[其他资源] 最短路问题的Floyd 算法优化及分析

[复制链接]

字体大小: 正常放大

雩风三日

395 主题	3 听众	5036 积分

TA的每日心情

	衰 2021-3-28 15:16

签到天数: 25 天

[LV.4]偶尔看看III

电梯直达

1^#

发表于 2020-12-29 15:33 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

最短路问题的Floyd 算法优化及分析

在传统Floyd 算法的基础上，运用动态规划思想通过迭代求出最终的最短路矩阵，并在迭代过程中先筛掉不能使路径权值变小的部分中间节点不参与迭代，从而简化计算权值矩阵的运算步骤，缩短矩阵运算时间。分析结果显示本文算法明显提高了运算的效率，降低了算法的复杂度。

关键词: 图论算法; 最短路问题; Floyd 算法