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

encounter a vertex that has not been processed. We use the scratch variable to
record it. Initially, scratch is 0. Thus, if the vertex is unprocessed, the test fails
at line 20, and we reach line 23. Then, when the vertex is processed, scratch is
set to 1 (at line 23). The priority queue might be empty if, for instance, some
of the vertices are unreachable. In that case, we can return immediately. The
loop at lines 26-40 is much like the loop in the unweighted algorithm. The
difference is that at line 29, we must extract cvw from the adjacency list entry,
ensure that the edge is nonnegative (otherwise, our algorithm could produce
incorrect answers), add cvw instead of 1 at lines 34 and 36, and add to the prior-
ity queue at line 38.

negative-weighted,
shortest-path problem

14.4

Dijkstra's algorithm requires that edge costs be nonnegative. This require-
ment is reasonable for most graph applications, but sometimes it is too
restrictive. In this section we briefly discuss the most general case: the negative-
weighted, shortest-path algorithm.

Negative edges
cause Dijkstra's
algorithm not to
work. An alterna-
tive algorithm is
needed.

negative-weighted, single-source, shortest-path problem
Find the shortest path (measured by total cost) from a designated vertex S to
every vertex. Edge costs may be negative.

14.4.1 theory

The proof of Dijkstra's algorithm required the condition that edge costs,
and thus paths, be nonnegative. Indeed, if the graph has negative edge costs,
Dijkstra's algorithm does not work. The problem is that, once a vertex v has
been processed, there may be, from some other unprocessed vertex u , a nega-
tive path back to v . In such a case, taking a path from S to u to v is better than
going from S to v without using u . If the latter were to happen, we would be in
trouble. Not only would the path to v be wrong, but we also would have to
revisit v because the distances of vertices reachable from v may be affected.
(In Exercise 14.10 you are asked to construct an explicit example; four verti-
ces suffice.)
We have an additional problem to worry about. Consider the graph shown
in Figure 14.28. The path from V 3 to V 4 has a cost of 2. However, a shorter
path exists by following the loop V 3 , V 4 , V 1 , V 3 , V 4 , which has a cost of -3.
This path is still not the shortest because we could stay in the loop arbitrarily
long. Thus the shortest path between these two points is undefined.

A negative-cost
cycle makes most,
if not all, paths
undefined because
we can stay in the
cycle arbitrarily long
and obtain an arbi-
trarily small
weighted path
length.