algorithm - Floyd-Warshall 算法 - 为什么这个顺序？

Question

在算法中，最短 [u,v,x] 有 3 个循环 x 从 1 - n， 你从 1 - n， v 从 1 - n。

为什么循环来自 x,u,v 而不是 x,v,u 或 u,v,x？

Answer 1

假设(u,v)是顶点的索引，x表示索引，以便我们找到顶点之间的最短距离 u和顶点 v只有中间的那些顶点编号为 <= x .

因此 dist[u,v,x] 的重复出现使用 dist[u,v,x-1] , dist[u,x,x-1]和 dist[x,v,x-1] .

由于在 u,v,x 的计算中涉及三个顶点 ( dist[u,v,x] ) , 所以我们应该已经计算出 dist计算前所有三对的 dist[u,v,x] .

因此，x 的循环必须是最外层的循环。内部循环可以是 v,u或 u,v因为两者都是顶点。