Floyd算法 最外层 迭代顺序 关系

Floyd 算法与最外层迭代顺序无关

这个算法可以计算出任意两点之间的最短路 （当然不包含负环 包含负环的图没有最短路！）

Floyd 算法在网上有很多解释 我就不赘述 在这里我想 证明一个我在理解过程中一的一个问题

当时看这个算法的时候 总觉得他的求最短路的过程中 和检查的点出现的顺序有关系 一觉醒来 终于发现了其中的原委！！！ （睡觉是多么骚的一个操作啊）

假设存u->v之间的最短路为 u->i->j->v

我们先假设他的迭代顺序（最外层循环）为 i , j

那么当以i开始检查时 寻找以i为中间点的 图中任意两个点 我们发现 u->i->j这条路可以更新u->j的距离

当以j为中间点迭代时 我们已经有了u->j 当检查到u->v 时 发现恰好可以用j点作为中间点 更新了 u->j->v

(u->i->j->v)

假设迭代顺序为 j,i

当我们以j 检查时 我们发现了 i->j->v可以更新 下一次以i 检查时 我们检查u->v时 发现恰好可以 u->i->v (u->i->j->v)

现在想想 其实这个问题不难 但是为了帮助走入这个误区的朋友 还是果断下下这篇心得。

FINISHED！