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

220 DIRECTED GRAPHS [CHAP. 9

Fromy:The successive vertices ares, entered for the first time, andt. Thus:

(1) Set(s)=(y)+k= 5 + 2 =7 andp(s)=p(y)s=uzys.

(2) We calculate:

(y)+k= 5 + 1 =6 which is less than (t)= 7.

Thus we change(t)andp(t)to read:

(t)=(y)+ 1 =6 and p(t)=p(y)t=uzyt.

Nowp(t)has been determined.

Fromr:The successive vertices arew, entered for the first time, ands. Thus:

(1) Set(w)=(r)+ 3 =11 andp(w)=p(r)w=uxrw.

(2) We calculate:

(r)+k= 8 + 2 =10 which is less than (s)= 7.

Thus we leave(s)andp(s)alone.

Notethatp(s)has been determined.

Froms:The successive vertex isw. We calculate:

(s)+k= 7 + 3 =10 which is less than (w)= 11.

Thus we change,(w)andp(w)to read:

(w)=(s)+ 3 =10 and p(w)=p(s)w=uzysw.

Fromt:The successive vertex isw. We calculate:

(t)+k= 6 + 3 =9 which is less than (w)= 10.

Thus we undate(w)andp(w)as follows:

(w)=(t)+ 3 =9 and p(w)=p(t)=uzytw

Nowp(w)has been determined.
The algorithm is finished sincep(w)has been determined. Thusp(w)=uzytwis the shortest path fromutow
and(w)=9.
The edges which were examined in the above example form the rooted tree in Fig. 9-20. This is the tree
in Fig. 9-19(b) which has been pruned at vertices belonging to longer partial paths. Observe that only 13 of the
original 23 edges of the tree had to be examined.

Fig. 9-20