Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 9] DIRECTED GRAPHS 209

The transitive closureR of the relationRonVmay now be viewed as the set of ordered pairs(u,v)such that
there is a path fromutovin the graphG. Furthermore, by the above discussion, we need only look at simple
paths of lengthm−1 or less and cycles of length m or less. Accordingly, we have the following result which
characterizes the transitive closureRofR.

Theorem 9.7: LetRbe a relation on a setVwithmelements. Then:

(i) R∗=R∪R^2 ∪...∪Rmis the transitive closure ofR.

(ii) The path matrixPofG(V, R)is the adjacency matrix ofG′(V, R*).

9.6Warshall’s Algorithm, Shortest Paths

LetGbe a directed graph withmvertices,v 1 ,v 2 ,..., vm. Suppose we want to find the path matrixPof the
graphG. Warshall gave an algorithm which is much more efficient than calculating the powers of the adjacency
matrixA. This algorithm is defined in this section, and a similar algorithm is used to find shortest paths inGwhen
Gis weighted.

Warshall’s Algorithm

First we definem-square Boolean matricesP 0 ,P 1 ,...,PmwherePk[i,j] denotes theijentry of the
matrixPk:

Pk[i, j]=

⎧

⎨

⎩

1 if there is a simple path fromvitovjwhich does not use any

other vertices except possiblyv 1 ,v 2 ,...,vk,

0 otherwise.

For example,

P 3 [i, j]=1 if there is a simple path fromvitovjwhich does not use any

other vertices except possiblyv 1 ,v 2 ,v 3.

Observe that the first matrixP 0 =A, the adjacency matrix ofG. Furthermore, sinceGhas onlymvertices, the
last matrixPm=P, the path matrix ofG.
Warshall observed thatPk[i,j]=1 can occur only if one of the following two cases occurs:

(1) There is a simple path fromvitovjwhich does not use any other vertices except possiblyv 1 ,v 2 ,...,vk− 1 ;

hence

Pk− 1 [i, j]= 1

(2) There is a simple path fromvitovkand a simple path fromvktovjwhere each simple path does not use

any other vertices except possiblyv 1 ,v 2 ,...,vk− 1 ; hence

Pk− 1 [i, k]=1 and Pk− 1 [k, j]= 1

These two cases are pictured as follows:

( 1 )vi→···→vj; ( 2 )vi→···→vk→···vj

where→ ··· →denotes part of a simple path which does not use any other vertices except possiblyv 1 ,v 2 ,...,
vk− 1. Accordingly, the elements ofPkcan be obtained by:

Pk[i, j]=Pk− 1 [i, j]∨(Pk− 1 [i, k]∧Pk− 1 [k, j])

where we use the logical operations of a∧(AND) and∨(OR). In other words we can obtain each entry in the
matrixPkby looking at only three entries in the matrixPk− 1. Warshall’s algorithm appears in Fig. 9-6.