时间戳

首页 > 解决方案 > Warshall 算法思想和可能的改进

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

问题描述

Warshall 用于计算有向图的传递闭包的算法通常采用以下形式（来自Warshall 算法思想和改进）：

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)

但是我们可以通过注意到没有更新 if |ij| 来加快上述实现。<= k，所以在这种情况下我们可以跳过运行更新。

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

标签： algorithmgraph-algorithm

解决方案

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

Warshal 算法在迭代 k 中所做的是确定在标记为i的顶点和标记为j 的顶点之间是否存在仅使用中间顶点{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] and R(k−1)[k, j]. 也就是说，存在从顶点 i 到顶点 k 的路径，并且存在从顶点 k 到顶点 j 的路径，每个路径仅使用中间的顶点{1, ..., k-1}作为中间。

ior的值j（就此而言）与 vertex和 vertex|i-j|之间的距离无关。它们是用作顶点标识符的任意标签。ij

推荐阅读