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 Section 22.2. 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 Section 22.2 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 Section 22.2, 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

1. V' is the set of vertices reachable from s in G,

2. G' forms a rooted tree with root s, and

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