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 次迭代中所做的是确定 标记为 i 的顶点和 标记为 j 的顶点之间是否存在路径仅使用 {1, ..., k} 中的顶点作为中间体。因此，如果满足以下两个条件之一，R(k)[i,j] 应等于 1：

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

i 或 j（以及 |i-j| 的值）与顶点 i 和顶点 [=12= 之间的距离无关].它们是用作顶点标识符的任意标签。

Warshall算法思想及可能的改进

Warshall algorithm idea and possible improvement

algorithm

graph-algorithm