M 3 is computed in a similar fashion:
M 3 = E
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0
1 1 1 1 0
U
M 4 and M 5 will be the same as M 3 ; row 4 is all 0s, so any row that gets or-ed
with it will be unchanged, and column 5 is all 0s so all rows are copied directly. In
terms of the graph, no new 1 entries are produced because there are no paths from
4 to any node or from any node to 5. Thus M 3 = M 4 = M 5 = R, as computed in
Example 5. Note, however, that the matrices computed by Warshall’s algorithm,
except for M 0 = A and M n = R, do not agree with the matrices that are powers of
A used in our previous algorithm for R.
Each pass through the outer loop of Warshall’s algorithm modifies in place
the matrix that existed at the end of the previous pass. Warshall’s algorithm requires no additional storage for other matrices, even though we wrote down new
matrices in our example. There is one more point we need to check. Because we
are modifying the (only) matrix as we go along, during any one pass through
the outer loop, some of the entries will belong to M k+1 while others still belong
to M k . Specifically, on pass k + 1, we may consider M 3i, k + 14 ` M 3k + 1, j 4
in Expression (5), where these values have already been computed on this pass
and therefore represent M k+l 3i, k + 1 4 and M k+1 3k + 1, j 4 rather than the values
M k 3i, k + 1 4 and M k 3k + 1, j 4 we used in our justification for this algorithm. Can
there be a case where the values M k+1 3i, k + 1 4 and M k+1 3k + 1, j 4 are 1, so that
a 1 value goes into M k+1 3i, j 4, whereas the values M k 3i, k + 1 4 and M k 3k + 1, j 4
are 0? No—if M k+1 3i, k + 1 4 = 1, there is a path from n i to n k+1 with interior
nodes drawn from the set 5n 1 , n 2 , … , n k+1 6. However, because n k+1 is an endpoint and cycles can be eliminated, there must also be a path with interior nodes
drawn from the set 5n 1 , n 2 , … , n k 6 so that M k 3i, k + 14 = 1. A similar argument
holds for M k+1 3k + 1, j 4.
Practice 6 Use Warshall’s algorithm (formally or informally) to compute R for the graph of Figure 7.2.
Compare your answer with that for Practice 5.
How much work does Warshall’s algorithm require as measured by the number of Boolean and/or operations? Consider the formal algorithm. The single assignment statement in the algorithm lies within a triply nested loop; it will be
executed n
3
times. Each execution of the assignment statement requires one and
and one or; therefore, the total amount of work is 2n
3
= Θ(n
3
). Recall that our
previous algorithm for computing R was an Θ(n
4
) algorithm.
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
565
■
M 3 = E
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0
1 1 1 1 0
U
M 4 and M 5 will be the same as M 3 ; row 4 is all 0s, so any row that gets or-ed
with it will be unchanged, and column 5 is all 0s so all rows are copied directly. In
terms of the graph, no new 1 entries are produced because there are no paths from
4 to any node or from any node to 5. Thus M 3 = M 4 = M 5 = R, as computed in
Example 5. Note, however, that the matrices computed by Warshall’s algorithm,
except for M 0 = A and M n = R, do not agree with the matrices that are powers of
A used in our previous algorithm for R.
Each pass through the outer loop of Warshall’s algorithm modifies in place
the matrix that existed at the end of the previous pass. Warshall’s algorithm requires no additional storage for other matrices, even though we wrote down new
matrices in our example. There is one more point we need to check. Because we
are modifying the (only) matrix as we go along, during any one pass through
the outer loop, some of the entries will belong to M k+1 while others still belong
to M k . Specifically, on pass k + 1, we may consider M 3i, k + 14 ` M 3k + 1, j 4
in Expression (5), where these values have already been computed on this pass
and therefore represent M k+l 3i, k + 1 4 and M k+1 3k + 1, j 4 rather than the values
M k 3i, k + 1 4 and M k 3k + 1, j 4 we used in our justification for this algorithm. Can
there be a case where the values M k+1 3i, k + 1 4 and M k+1 3k + 1, j 4 are 1, so that
a 1 value goes into M k+1 3i, j 4, whereas the values M k 3i, k + 1 4 and M k 3k + 1, j 4
are 0? No—if M k+1 3i, k + 1 4 = 1, there is a path from n i to n k+1 with interior
nodes drawn from the set 5n 1 , n 2 , … , n k+1 6. However, because n k+1 is an endpoint and cycles can be eliminated, there must also be a path with interior nodes
drawn from the set 5n 1 , n 2 , … , n k 6 so that M k 3i, k + 14 = 1. A similar argument
holds for M k+1 3k + 1, j 4.
Practice 6 Use Warshall’s algorithm (formally or informally) to compute R for the graph of Figure 7.2.
Compare your answer with that for Practice 5.
How much work does Warshall’s algorithm require as measured by the number of Boolean and/or operations? Consider the formal algorithm. The single assignment statement in the algorithm lies within a triply nested loop; it will be
executed n
3
times. Each execution of the assignment statement requires one and
and one or; therefore, the total amount of work is 2n
3
= Θ(n
3
). Recall that our
previous algorithm for computing R was an Θ(n
4
) algorithm.
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
565
■