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

210 DIRECTED GRAPHS [CHAP. 9

Fig. 9-6

Shortest-path Algorithm

LetGbe a simple directed graph withmvertices,v 1 ,v 2 ,...,vm. SupposeGis weighted; that is, suppose each
edgeeofGis assigned a nonnegative numberw(e)called theweightorlengthofe. ThenGmay be maintained
in memory by its weight matrixW=[wij] defined as follows:

wij=

{

w(e) if there is an edgeefromvitovj

0 if there is no edge fromvitovj

The path matrixPtells us whether or not there are paths between the vertices. Now we want to find a matrixQ
which tells us the lengths of the shortest paths between the vertices or, more exactly, a matrixQ=[qij]where

qij=length of the shortest path fromvitovj

Next we describe a modification of Warshall’s algorithm which efficiently finds us the matrixQ.
Here we define a sequence of matricesQ 0 ,Q 1 ,...,Qm(analogous to the above matricesP 0 ,P 1 ,...,Pm)
whereQk[i,j], theijentry ofQk, is defined as follows:
Qk[i,j]=the smaller of the length of the preceding path fromvitovjor the sum of the lengths of the
preceding paths fromvitovkand fromvktovj.
More exactly,
Qk[i, j]=MIN(Qk− 1 [i, j],Qk− 1 [i, k]+Qk− 1 [k, j])

The initial matrixQ 0 is the same as the weight matrixWexcept that each 0 inwis replaced by∞(or a very,
very large number). The final matrixQmwill be the desired matrixQ.

EXAMPLE 9.9 Figure 9-7 shows a weighted graphGand its weight matrixWwhere we assume thatv 1 =R,
v 2 =S,v 3 =T,v 4 =U.
Suppose we apply the modified Warshall’s algorithm to our weighted graphGin Fig. 9-7. We will obtain
the matricesQ 0 ,Q 1 ,Q 3 , andQ 4 in Fig. 9-8. (To the right of each matrixQkin Fig. 9-8, we show the matrix of