Graphs and paths - Data Structures and Problem Solving Using Java - page 547

We begin by examining how to alter D w . In solving the unweighted
shortest-path problem, if D w =

We use D v + c v, w
as the new dis-
tance and to decide
whether the dis-
tance should be
updated.

∞

, we set D w = D v + 1 because we lower the
value of D w if vertex v offers a shorter path to w . The dynamics of the algo-
rithm ensure that we need alter D w only once. We add 1 to D v because the
length of the path to w is 1 more than the length of the path to v . If we apply
this logic to the weighted case, we should set D w = D v + c v, w if this new value
of D w is better than the original value. However, we are no longer guaranteed
that D w is altered only once. Consequently, D w should be altered if its current
value is larger than D v + c v, w (rather than merely testing against

∞

). Put sim-
ply, the algorithm decides whether v should be used on the path to w . The
original cost D w is the cost without using v ; the cost D v + c v, w is the cheapest
path using v (so far).

Figure 14.23 shows a typical situation. Earlier in the algorithm, w had its
distance lowered to 8 when the eyeball visited vertex u . However, when the eye-
ball visits vertex v , vertex w needs to have its distance lowered to 6 because we
have a new shortest path. This result never occurs in the unweighted algorithm
because all edges add 1 to the path length, so

A queue is no
longer appropriate
for storing vertices
awaiting an eyeball
visit.

D u D v ≤ implies D u + 1 ≤ D v + 1

and thus D w D v ≤ + 1 . Here, even though D u D v ≤

, we can still improve the

path to w by considering v .

Figure 14.23 illustrates another important point. When w has its distance
lowered, it does so only because it is adjacent to some vertex that has been
visited by the eyeball. For instance, after the eyeball visits v and processing
has been completed, the value of D w is 6 and the last vertex on the path is a
vertex that has been visited by the eyeball. Similarly, the vertex prior to v
must also have been visited by the eyeball, and so on. Thus at any point the
value of D w represents a path from S to w using only vertices that have been
visited by the eyeball as intermediate nodes. This crucial fact gives us Theo-
rem 14.1.

The distance for
unvisited vertices
represents a path
with only visited
vertices
as intermediate
nodes.

figure 14.23
The eyeball is at v and
w is adjacent, so D w
should be lowered
to 6.

3 8

3

v w

0

S

6

2

u