Reputation: 7305
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
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:
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.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