algoRitHm Warshall’s algorithm
Warshall(n × n Boolean matrix M)
//Initially, M = adjacency matrix of a directed graph G with no parallel arcs
for k = 0 to n − 1 do
for i = 1 to n do
for j = 1 to n do
M 3i, j 4 = M 3i, j 4 ~ (M 3i, k + 1 4 ` M 3k + 1, j 4)
end for
end for
end for
//at termination, M = reachability matrix of G
end Warshall
This pseudocode gives a nice neat description of Warshall’s algorithm, which can
be implemented as computer code rather easily. These steps are confusing to do by
hand, however, requiring some bookkeeping to keep track of all the indices. We can
write the algorithm more informally, making it easier to do manually. Suppose again
that matrix M k in the sequence exists and we are trying to write row i of the next
matrix in the sequence. For the various values of j, we must evaluate the expression
M 3i, j 4 ~ (M 3i, k + 1 4 ` M 3k + 1, j 4)
(5)
If entry M 3i, k + 14 is 0, then M 3i, k + 1 4 ` M 3k + 1, j 4 = 0 for all j. Expression
(5) then reduces to
M 3i, j 4 ~ 0 = M 3i, j 4
In other words, row i of the matrix remains unchanged. If, on the other hand,
entry M 3i, k + 1 4 is 1, then M 3i, k + 1 4 ` M 3k + 1, j 4 = M 3k + 1, j 4 for all j.
Expression (5) then becomes
M 3i, j 4 ~ M 3k + 1, j 4
In other words, row i of the matrix becomes the Boolean or of the current row i
and the current row k + 1.
Table 7.1 describes the (informal) steps to compute entries in M k+1 from
matrix M k .
table 7.1
1. Consider column k + 1 in m k .
2. For each row with a 0 entry in this column, copy that row to m k+1 .
3. For each row with a 1 entry in this column, or that row with row k + 1 and write
the resulting row in m k+1 .
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
563