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

218 DIRECTED GRAPHS [CHAP. 9

Fig. 9-18

EXAMPLE 9.12 SupposeAlgorithm 9.4 is applied to the graphSin Fig. 9-16. We obtain the following sequence
of the elements of QUEUE and sequence of vertices being processed:

QUEUE GEB DGE DG FAD FA CF C 


Vertex B E G D A F C

Thus the vertices are processed in the order:B,E,G,D,A,F.

9.10Pruning Algorithm for Shortest Path

LetGbe a weighted directed cycle-free graph. We seek the shortest path between two vertices, sayuandw.
We assumeGis finite so at each step there is a finite number of moves. SinceGis cycle-free, all paths between
uandwcan be given by a rooted tree withuas the root. Figure 9-19(b) enumerates all the paths betweenuand
win the graph in Fig. 9-19(a).

Fig. 9-19

One way to find the shortest path betweenuandwis simply to compute the lengths of all the paths of the
corresponding rooted tree. On the other hand, suppose two partial paths lead to an intermediate vertexv. From
then on, we need only consider the shorter partial path; that is, we prune the tree at the vertex corresponding to
the longer partial path. This pruning algorithm is described below.