algorithm - Warshall算法思想及可能的改进

Question

用于计算有向图的传递闭包的 Warshall 算法通常采用以下形式(来自 Warshall algorithm idea and improvement):

ALGORITHM Warshall(A[1..n, 1..n])
    //ImplementsWarshall’s algorithm for computing the transitive closure
    //Input: The adjacency matrix A of a digraph with n vertices
    //Output: The transitive closure of the digraph
    R(0) ←A
    for k←1 to n do
        for i ←1 to n do
            for j ←1 to n do
                R(k)[i, j ]←R(k−1)[i, j ] or (R(k−1)[i, k] and R(k−1)[k, j])
    return R(n)

但是我们可以通过注意到如果 |i-j| 没有更新来加快上面的实现<= k，所以在这种情况下我们可以跳过运行更新。

我错过了什么吗？这种改进不会影响运行时间吗？ (我还没有花时间计算那个版本的运行时间。)

Answer 1

您缺少的是 |i - j| 与 i 和 j 之间的距离无关。

Warshal 算法在第 k 次迭代中所做的是仅使用 { 1, ..., k} 作为中间体。因此，如果满足以下两个条件之一，R(k)[i,j] 应等于 1:

1. R(k-1)[i,j] = 1。也就是说，在顶点 i 和顶点 j 之间存在一条仅使用 {1, ..., k-1} 中的顶点作为中间节点的路径。
2. R(k−1)[i, k] 和 R(k−1)[k, j]。也就是说，存在一条从顶点 i 到顶点 k 的路径，并且存在一条从顶点 k 到顶点 j 的路径，每个路径仅使用 {1, ..., k-1} 中的顶点作为中间值.

i 或 j(和 |i-j| 的值)与顶点 之间的距离无关>i 和顶点 j。它们是用作顶点标识符的任意标签。