CODEWITHSUNDEEP
algorithmgraph-algorithm
KGhatak
KGhatak

Reputation: 7305

Warshall algorithm idea and possible improvement

Warshall's algorithm for computing the transitive closure of a digraph typically takes the following form (from 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)

But we could speed up the above implementation by noticing that there is no update if |i-j| <= k, so we can skip running the update in that case.

Am I missing something? Does this kind of improvement not impact the runtime? (I haven't taken the time yet to calculate the runtime for that version.)

Upvotes: 1

Views: 117

Answers (1)

snakile
snakile

Reputation: 54561

What you're missing is that |i - j| is not related to the distance between i and j.

What Warshal's Algorithm does at iteration k is to determine if there exists a path between the vertex labeled i and the vertex labeled j using only vertices among {1, ..., k} as intermediates. Hence, R(k)[i,j] should equal to 1 if any one of the following two conditions holds:

  1. R(k-1)[i,j] = 1. That is, there exists a path between vertex i and vertex j using only vertices among {1, ..., k-1} as intermediates.
  2. R(k−1)[i, k] and R(k−1)[k, j]. That is, there exists a path from vertex i to vertex k and there exists a path from vertex k to vertex j, each using only vertices among {1, ..., k-1} as intermediates.

The values of i or j (and |i-j| for that matter) have nothing to do with the distances between vertex i and vertex j. They're arbitrary labels serving as identifiers for the vertices.

Upvotes: 2

Related Questions