CHAP. 9] DIRECTED GRAPHS 219
Pruning Algorithm
This algorithm finds the shortest path between a vertexuand a vertexwin a weighted directed cycle-free
graphG. The algorithm has the following properties:
(a) During the algorithm each vertexv′ofGis assigned two things:(1) A number(v′)denoting the current minimal length of a path fromutov′.
(2) A pathp(v′)fromutov′of length(v′).
(b) Initially, we set(u)=0 andp(u)=u. Every other vertexvis initially assigned(v)=∞andp(v)=.(c) Each step of the algorithm examines an edgee=(v′,v) fromv′tovwith, say, lengthk. We calculate(v′)+k.(1) Suppose(v′)+k < (v). Then we have found a shorter path fromutov. Thus we update:
(v)=(v′)+k and p(v)=p(v′)v
(This is always true when(v)=∞, that is, when we first enter the vertexv.)
(2) Otherwise, we do not change(v)andp(v).If no other unexamined edges enterv, we will say thatp(v)has been determined.
(d) The algorithm ends whenp(w)has been determined.Remark: The edgee=(v′,v)in(c)can only be chosen ifv′has been previously visited, that is, ifp(v′)is not
empty. Furthermore, it is usually best to examine an edge which begins at a vertexv′whose pathp(v′)has been
determined.
EXAMPLE 9.13 We apply the pruning algorithm to the graphGin Fig. 9-19(a).
Fromu:The successive vertices arex,y, andz, which are all entered for the first time. Thus:
( 1 ) set(x)= 4 , p(x)=ux.
( 2 ) set(y)= 6 , p(y)=uy.
( 3 ) set(z)= 2 , p(z)=uz.
Note thatp(x)andp(z)have been determined.Fromx:The successive vertices arer, entered for the first time, andy. Thus:
(1) Set(r)= 4 + 4 =8 andp(r)=p(x)r=uxr.
(2) We calculate:
(x)+k= 4 + 3 =7 which is not less than (y)= 6.
Thus we leave(y)andp(y)alone.
Note thatp(r)has been determined.Fromz:The successivevertices aret, entered for the first time, andy. Thus:
(1) Set(t)=(z)+k= 2 + 5 =7 andp(t)=p(z)t=urt.
(2) We calculate:
(z)+k= 2 + 3 =5 which is less than (y)= 6.
We have found a shorter path toy, and so we update(y)andp(y); set:
(y)=(z)+k=5 and p(y)=p(z)y=uzyNowp(y)has been determined.