< Day Day Up > |
In some instances of the single-source shortest-paths problem, there may be edges whose weights are negative. If the graph G = (V, E) contains no negative-weight cycles reachable from the source s, then for all v ∈ V , the shortest-path weight δ(s, v) remains well defined, even if it has a negative value. If there is a negative-weight cycle reachable from s, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest path-a lesser-weight path can always be found that follows the proposed "shortest" path and then traverses the negative-weight cycle. If there is a negative-weight cycle on some path from s to v, we define δ(s, v) = -∞.
Figure 24.1 illustrates the effect of negative weights and negative-weight cycles on shortest-path weights. Because there is only one path from s to a (the path <s, a>), δ(s, a) = w(s, a) = 3. Similarly, there is only one path from s to b, and so δ(s, b) = w(s, a) + w(a, b) = 3 + (-4) = -1. There are infinitely many paths from s to c: <s, c>, <s, c, d, c>, <s, c, d, c, d, c>, and so on. Because the cycle <c, d, c> has weight 6 + (-3) = 3 > 0, the shortest path from s to c is <s, c>, with weight δ(s, c) = 5. Similarly, the shortest path from s to d is <s, c, d>, with weight δ(s, d) = w(s, c) + w(c, d) = 11. Analogously, there are infinitely many paths from s to e: <s, e>, <s, e, f, e>, <s, e, f, e, f, e>, and so on. Since the cycle <e, f, e> has weight 3 + (-6) = -3 < 0, however, there is no shortest path from s to e. By traversing the negative-weight cycle <e, f, e> arbitrarily many times, we can find paths from s to e with arbitrarily large negative weights, and so δ(s, e) = -∞. Similarly, δ(s, f) = -∞. Because g is reachable from f , we can also find paths with arbitrarily large negative weights from s to g, and δ(s, g) = -∞. Vertices h, i, and j also form a negative-weight cycle. They are not reachable from s, however, and so δ(s, h) = δ(s, i) = δ(s, j) = ∞.
Some shortest-paths algorithms, such as Dijkstra's algorithm, assume that all edge weights in the input graph are nonnegative, as in the road-map example. Others, such as the Bellman-Ford algorithm, allow negative-weight edges in the input graph and produce a correct answer as long as no negative-weight cycles are reachable from the source. Typically, if there is such a negative-weight cycle, the algorithm can detect and report its existence.
< Day Day Up > |