Negative-weight edges

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) = ∞.

Figure 24.1: Negative edge weights in a directed graph. Shown within each vertex is its shortest-path weight from source s. Because vertices e and f form a negative-weight cycle reachable from s, they have shortest-path weights of -∞. Because vertex g is reachable from a vertex whose shortest-path weight is -∞, it, too, has a shortest-path weight of -∞. Vertices such as h, i, and j are not reachable from s, and so their shortest-path weights are ∞, even though they lie on a negative-weight cycle.

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. Oth ers, 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.