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

CHAP. 9] DIRECTED GRAPHS 211

Fig. 9-7

paths which correspond to the lengths in the matrixQk.) The entries in the matrixQ 0 are the same as the weight
matrixWexcept each 0 inWis replaced by∞(a very large number). We indicate how the circled entries are
obtained:
Q 1 [ 4 , 2 ]=MIN(Q 0 [ 4 , 2 ],Q 0 [ 4 , 1 ]+Q 0 [ 1 , 2 ])=MIN(∞, 4 + 5 )= 9
Q 2 [ 1 , 3 ]=MIN(Q 1 [ 1 , 3 ],Q 1 [ 1 , 2 ]+Q 1 [ 2 , 3 ])=MIN(∞, 5 +∞)=∞
Q 3 [ 4 , 2 ]=MIN(Q 2 [ 4 , 2 ],Q 2 [ 4 , 3 ]+Q 2 [ 3 , 2 ])=MIN( 9 , 3 + 1 )= 4
Q 4 [ 3 , 1 ]=MIN(Q 3 [ 3 , 1 ],Q 3 [ 3 , 4 ]+Q 3 [ 4 , 1 ])=MIN( 10 , 5 + 4 )= 9

The last matrixQ 4 =Q, the desired shortest-path matrix.

Fig. 9-8

9.7Linked Representation of Directed Graphs

LetGbe a directed graph withmvertices. Suppose the number of edges ofGisO(m)or evenO(mlogm),

that is, supposeGis sparse. Then the adjacency matrixAofGwill contain many zeros; hence a great deal of