Single-source Shortest Paths

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. 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.

Cycles: Can a shortest path contain a cycle? As we have just seen, it cannot contain a negative-weight cycle. Nor can it contain a positive-weight cycle, since removing the cycle from the path produces a path with the same source and destination vertices and a lower path weight. That is, if p = 〈v₀, v₁,..., v_k〉 is a path and c = 〈v_i, v_{i 1},..., v_j〉 is a positive-weight cycle on this path (so that v_i = v_j and w(c) > 0), then the path p' = 〈v₀, v₁,..., v_i, v_{j 1}, v_{j 2},..., v_k〉 has weight w(p') = w(p) - w(c) < w(p), and so p cannot be a shortest path from v₀ to v_k.

That leaves only 0-weight cycles. We can remove a 0-weight cycle from any path to produce another path whose weight is the same. Thus, if there is a shortest path from a source vertex s to a destination vertex v that contains a 0-weight cycle, then there is another shortest path from s to v without this cycle. As long as a shortest path has 0-weight cycles, we can repeatedly remove these cycles from the path until we have a shortest path that is cycle-free. Therefore, without loss of generality we can assume that when we are finding shortest paths, they have no cycles. Since any acyclic path in a graph G = (V, E) contains at most |V| distinct vertices, it also contains at most |V| - 1 edges. Thus, we can restrict our attention to shortest paths of at most |V| - 1 edges.

Representing shortest paths: We often wish to compute not only shortest-path weights, but the vertices on shortest paths as well. The representation we use for shortest paths is similar to the one we used for breadth-first trees in Breadth-first search. Given a graph G = (V, E), we maintain for each vertex v V a predecessor π[v] that is either another vertex or NIL. The shortest-paths algorithms in this chapter set the π attributes so that the chain of predecessors originating at a vertex v runs backwards along a shortest path from s to v. Thus, given a vertex v for which π[v] ≠ NIL, the procedure PRINT-PATH(G, s, v) from Breadth-first search can be used to print a shortest path from s to v.

During the execution of a shortest-paths algorithm, however, the π values need not indicate shortest paths. As in breadth-first search, we shall be interested in the predecessor subgraph G_π = (V_π, E_π) induced by the π values. Here again, we define the vertex set V_π to be the set of vertices of G with non-NIL predecessors, plus the source s:

V_π = {v ∈ V :π[v] ≠ NIL} ∪ {s} .

The directed edge set E_π is the set of edges induced by the π values for vertices in V_π:

E_π = {(π[v], v) ∈ E : v ∈ V_π - {s}} .

We shall prove that the π values produced by the algorithms in this chapter have the property that at termination G_π is a "shortest-paths tree"-informally, a rooted tree containing a shortest path from the source s to every vertex that is reachable from s. A shortest-paths tree is like the breadth-first tree from Breadth-first search, but it contains shortest paths from the source defined in terms of edge weights instead of numbers of edges. To be precise, let G = (V, E) be a weighted, directed graph with weight function w : E → R, and assume that G contains no negative-weight cycles reachable from the source vertex s ∈ V , so that shortest paths are well defined. A shortest-paths tree rooted at s is a directed subgraph G' = (V', E'), where V' ⊆ V and E' ⊆ E, such that

V' is the set of vertices reachable from s in G,
G' forms a rooted tree with root s, and
for all v ∈ V', the unique simple path from s to v in G' is a shortest path from s to v in G.

Shortest paths are not necessarily unique, and neither are shortest-paths trees. For example, Figure 24.2 shows a weighted, directed graph and two shortest-paths trees with the same root.

Figure 24.2: (a) A weighted, directed graph with shortest-path weights from source s. (b) The shaded edges form a shortest-paths tree rooted at the source s. (c) Another shortest-paths tree with the same root.