562
Graph Algorithms
multiplication of two n × n Boolean matrices requires Θ(n
3
) Boolean and/or
operations. The algorithm to compute r requires n − 1 Boolean matrix multiplications (to find the products a
(2)
, a
(3)
, … , a
(n)
). To compute n − 1 such products
require (n − 1)Θ(n
3
) = Θ(n
4
) Boolean operations. To compute C ~ D where C
and D are two n × n Boolean matrices requires n
2
Boolean or operations. To compute r, n − 1 such matrix operations are required, so (n − 1)n
2
= Θ(n
3
) Boolean
or operations are performed. The total amount of work is Θ(n
4
) + Θ( n
3
) = Θ(n
4
).
Next we discuss a more efficient algorithm for computing the transitive
closure of a relation (or the reachability matrix of a graph).
Warshall’s Algorithm
For a graph G with n nodes, Warshall’s algorithm computes a sequence of n + 1
matrices M 0 , M 1 , M 2 , … , M n . For each k, 0 ≤ k ≤ n, M k 3i, j 4 = 1 if and only if
there is a path in G from n i to n j whose interior nodes (i.e., nodes that are not the
endpoints of the path) come only from the set of nodes 5n 1 , n 2 , … , n k 6.
Let us examine the “end conditions.” When k = 0, the set 5n 1 , n 2 , … , n 0 6 is
the empty set, so M 0 3i, j 4 = 1 if and only if there is a path in G from n i to n j whose
interior nodes come from the empty set; that is, there are no interior nodes. The
path from n i to n j must then consist only of the endpoints and one connecting arc,
so n i and n j are adjacent nodes. Thus M 0 = a. The other end condition occurs
when k = n. Then the set 5n 1 , n 2 , … , n n 6 consists of all the nodes in G, so there is
really no restriction at all on the interior nodes in the path and M n 3i, j 4 = 1 if and
only if there is a path from n i to n j , which means that M n = r.
Therefore Warshall’s algorithm begins with a = M 0 and successively computes M 1 , M 2 , … , M n = r. This computation can be defined inductively. The
base case is to let M 0 = a. Now assume that M k has been computed, and consider
how to compute M k+1 or, more specifically, M k+1 3i, j 4. We have M k+1 3i, j 4 = 1
if and only if there is a path from n i to n j whose interior nodes come only from the
set 5n 1 , n 2 , … , n k+1 6. This can happen in two ways:
1. All the interior nodes come from 5n 1 , n 2 , … , n k 6, in which case
M k 3i, j 4 = 1. We should therefore carry forward any 1 entries in M k into
M k+1 .
2. Node n k+1 is an interior node. We can assume that n k+1 is an interior node
only once, because cycles can be eliminated from a path. Then there must
be a path from n i to n k+1 whose interior nodes come from 5n 1 , n 2 , … , n k 6
and a path from n k+1 to n j whose interior nodes come from 5n 1 , n 2 , … , n k 6.
This means that M k 3i, k + 1 4 = 1 and M k 3k + 1, j 4 = 1, which is to say
that M k 3i, k + 14 ` M k 3k + 1, j 4 = 1; this condition can be tested because our assumption is that M k has already been computed.
In the following pseudocode version of Warshall’s algorithm, the initial value
of matrix M is a. Each pass through the outer loop computes the next matrix in
the sequence M 1 , M 2 , … , M n = r.
Graph Algorithms
multiplication of two n × n Boolean matrices requires Θ(n
3
) Boolean and/or
operations. The algorithm to compute r requires n − 1 Boolean matrix multiplications (to find the products a
(2)
, a
(3)
, … , a
(n)
). To compute n − 1 such products
require (n − 1)Θ(n
3
) = Θ(n
4
) Boolean operations. To compute C ~ D where C
and D are two n × n Boolean matrices requires n
2
Boolean or operations. To compute r, n − 1 such matrix operations are required, so (n − 1)n
2
= Θ(n
3
) Boolean
or operations are performed. The total amount of work is Θ(n
4
) + Θ( n
3
) = Θ(n
4
).
Next we discuss a more efficient algorithm for computing the transitive
closure of a relation (or the reachability matrix of a graph).
Warshall’s Algorithm
For a graph G with n nodes, Warshall’s algorithm computes a sequence of n + 1
matrices M 0 , M 1 , M 2 , … , M n . For each k, 0 ≤ k ≤ n, M k 3i, j 4 = 1 if and only if
there is a path in G from n i to n j whose interior nodes (i.e., nodes that are not the
endpoints of the path) come only from the set of nodes 5n 1 , n 2 , … , n k 6.
Let us examine the “end conditions.” When k = 0, the set 5n 1 , n 2 , … , n 0 6 is
the empty set, so M 0 3i, j 4 = 1 if and only if there is a path in G from n i to n j whose
interior nodes come from the empty set; that is, there are no interior nodes. The
path from n i to n j must then consist only of the endpoints and one connecting arc,
so n i and n j are adjacent nodes. Thus M 0 = a. The other end condition occurs
when k = n. Then the set 5n 1 , n 2 , … , n n 6 consists of all the nodes in G, so there is
really no restriction at all on the interior nodes in the path and M n 3i, j 4 = 1 if and
only if there is a path from n i to n j , which means that M n = r.
Therefore Warshall’s algorithm begins with a = M 0 and successively computes M 1 , M 2 , … , M n = r. This computation can be defined inductively. The
base case is to let M 0 = a. Now assume that M k has been computed, and consider
how to compute M k+1 or, more specifically, M k+1 3i, j 4. We have M k+1 3i, j 4 = 1
if and only if there is a path from n i to n j whose interior nodes come only from the
set 5n 1 , n 2 , … , n k+1 6. This can happen in two ways:
1. All the interior nodes come from 5n 1 , n 2 , … , n k 6, in which case
M k 3i, j 4 = 1. We should therefore carry forward any 1 entries in M k into
M k+1 .
2. Node n k+1 is an interior node. We can assume that n k+1 is an interior node
only once, because cycles can be eliminated from a path. Then there must
be a path from n i to n k+1 whose interior nodes come from 5n 1 , n 2 , … , n k 6
and a path from n k+1 to n j whose interior nodes come from 5n 1 , n 2 , … , n k 6.
This means that M k 3i, k + 1 4 = 1 and M k 3k + 1, j 4 = 1, which is to say
that M k 3i, k + 14 ` M k 3k + 1, j 4 = 1; this condition can be tested because our assumption is that M k has already been computed.
In the following pseudocode version of Warshall’s algorithm, the initial value
of matrix M is a. Each pass through the outer loop computes the next matrix in
the sequence M 1 , M 2 , … , M n = r.