为什么 Floyd-Warshall 中 3 个循环的顺序很重要？

Question

在流行的实现中，我们使用三个循环，循环变量说 i,j,k。这里 i 和 j 分别用于指示两个顶点的源和目的地，因此“k”代表“中间”顶点。如果我将循环与循环变量“k”放在第 3 位而不是第 1 位，我会得到错误的答案。为什么？

Answer 1

这是 Floyd-Warshall 算法背后的想法：

if:
i is connected to k and
k is connected to j
then if i and j are not connected,
create a connection between i and j

替代解释：

if:
i -> k and
k -> j
then if not i -> j
create i -> j

我想说的是 k 将处于逻辑连接的中间。中间顶点 k 负责允许 N 个相邻顶点有直接连接。

上述算法必须应用于|V| 顶点，因此 k 上的循环必须是最外层的 for 循环。

例子：

DiGraph:
Vertices: 0,1,2
Edges: (0,1), (1,2)
Representation: 0 -> 1 -> 2   

算法：

k = 0
i = 0 ignore because k = i
i = 1 false because 1 -> 0 is wrong
i = 2 false because 2 -> 0 is wrong

k = 1
i = 0 true because 0 -> 1
j = 0 ignore because i = j
j = 1 ignore because j = k
j = 2 true because 1 -> 2
Since 0 -> 2 does not exist, create this edge
i = 1 ignore because i = k
i = 2 false because 2 -> 1 is wrong

k = 2
i = 0 true because we created this edge in the previous iteration
j = 0 ignore because i = j
j = 1 false because 2 -> 1 is wrong
j = 2 ignore because j = k
i = 1 true because 1 -> 2
j = 0 false because 2 -> 0 is wrong
j = 1 ignore because i = j
j = 2 ignore because j = k
i = 2 ignore because i = k

所以总而言之，
k 需要执行 |V| 次
我需要执行| V |
执行 |V| 所需的每个 k j 的次数 i -> k 上每个成功 i 的次数

时间复杂度：O(n ³ )

注意：如果您想应用该算法或使用它以更好地了解它的工作原理，请查看我在 GraphADT 上的 Github 存储库，方法名称是transitiveClosure(). 该方法在Graph.java 文件中实现。