Finding a shortest path

When you reach for it

You have a weighted graph, or a weighted directed graph, whose weights are all \ge 0: miles, minutes or dollars. You have a start s, and you want the weighted distance d_w(s, v) of Weighted and directed graphs to every vertex v, with a cheapest route. Listing every path works for five vertices, but in a network where every two of 10 places are joined there are 109{,}601 paths between two of them (Example 7). Dijkstra’s algorithm finds every distance from s in about v rounds for v vertices.

This lesson takes two days. Day 1 is the method, the route it records, and the proof that it is right (Theorem 1, Examples 1 to 3). Day 2 is the tree of routes, the subpath property, directed graphs, unweighted graphs, negative weights and the count of the work (Theorems 2 and 3, Examples 4 to 7).

Walks, paths and the plain distance d are those of Walks, paths, cycles and connected graphs. Weights here may be 0. A cheapest walk may then repeat a vertex, but cutting out the repeat removes a stretch of weight \ge 0, so d_w(s, v) is still the least weight of a path from s to v.

The procedure

Day 1: settling one vertex a round

The method keeps a set S of settled vertices, whose distances from s are known. Every vertex v carries a label \ell(v), the weight of the cheapest route to v found so far, and a predecessor p(v), the vertex before v on that route. At the start S is empty, \ell(s) = 0, and \ell(v) = \infty for every other v.

Each round settles one unsettled vertex u of least label, any one if several tie, and then scans it: for each unsettled neighbor x of u, the route to u followed by the edge ux is compared with the best route to x so far,

If \ell(u) + w(ux) < \ell(x), strictly, the label drops to \ell(u) + w(ux) and p(x) becomes u. The run stops when every vertex is settled or the least unsettled label is \infty; the vertices left then cannot be reached from s (Exercise 7).

Only u is scanned because every other settled vertex was scanned when it was settled. Settling the least label is the heart of the method: any route to that vertex leaves the settled set somewhere, and Theorem 1 shows that leaving already costs at least that label.

Theorem 1 (settled labels are distances). Let every weight be \ge 0 and run the method from s. (a) When a vertex u is settled, \ell(u) = d_w(s, u), and the label never changes after. (b) For a settled u \ne s, following predecessors back from u reaches s without repeating a vertex, and this path, read from s, is a cheapest path from s to u.

Proof. Only unsettled vertices are scanned, so a settled label never changes. Next, every finite label is the weight of a walk from s: at the start the only finite label is \ell(s) = 0, the weight of the walk (s), and a change sets \ell(x) = \ell(u) + w(ux), the weight of a walk to u extended by the edge ux. So \ell(x) \ge d_w(s, x) whenever \ell(x) is finite.

For (a), induct on the order of settling, u_1, u_2, \ldots. First u_1 = s, with \ell(s) = 0 = d_w(s, s). Suppose u_1, \ldots, u_{j-1} were settled with correct labels, let u = u_j, and let S = \{u_1, \ldots, u_{j-1}\}. The run never settles a label \infty, so u is reachable; let P be a cheapest path from s to u. It starts in S and ends outside, so it has a first vertex y outside S, with x the vertex before it. Then x = u_i for some i < j, so \ell(x) = d_w(s, x), and when x was scanned y was unsettled, so \ell(y) became at most d_w(s, x) + w(xy); labels never rise. The part of P from s to x is a walk, so it weighs at least d_w(s, x). Therefore

where the last \le holds because the rest of P, from y to u, has weights \ge 0. The run chose u with least label among unsettled vertices, and y is unsettled, so \ell(u) \le \ell(y) \le d_w(s, u). With \ell(u) \ge d_w(s, u), equality holds.

For (b), p(x) = u is set while u is scanned, so p(x) was settled before x. Going back along predecessors, the order of settling strictly falls, so no vertex repeats, and the chain stops only at s, the one settled vertex whose label was never lowered. When p(x) = u was last set, \ell(x) = \ell(u) + w(ux), and neither number changes afterward. Adding along the chain, the path weighs \ell(u) = d_w(s, u). \square

The proof uses w \ge 0 in one place only: the rest of P weighs at least 0. Example 6 shows the method failing without it.

Day 2: the tree of routes and the subpath property

Theorem 2 (the shortest-path tree). After a run from s, let R be the set of settled vertices. The edges p(x)x for x \in R, x \ne s, form a tree T with vertex set R, and for each x \in R the path from s to x in T is a cheapest path in G.

Proof. Each x \ne s in R gives one edge, and two vertices never give the same edge, since p(x) = y and p(y) = x would make each settled before the other. So T has \lvert R \rvert - 1 edges. Every x is joined to s by its predecessor chain, so T is connected, and a connected graph with one edge fewer than its vertices is a tree (Trees, Result 7). A tree has exactly one path between two vertices, so the path from s to x in T is the predecessor chain, a cheapest path by Theorem 1(b). \square

The tree is a shortest-path tree from s. One predecessor per vertex is enough to store every cheapest route because of the next fact.

Theorem 3 (the subpath property). Let every weight be \ge 0, and let P = (v_0, v_1, \ldots, v_k) be a cheapest path from v_0 to v_k. Then for 0 \le i \le j \le k, the part (v_i, \ldots, v_j) is a cheapest path from v_i to v_j.

Proof. Suppose some walk Q from v_i to v_j weighs less than (v_i, \ldots, v_j). Follow P from v_0 to v_i, then Q, then P from v_j to v_k. This is a walk from v_0 to v_k whose weight is w(P) minus the weight of (v_i, \ldots, v_j) plus w(Q), less than w(P) = d_w(v_0, v_k). No walk weighs less than d_w(v_0, v_k), a contradiction. \square

Directed graphs. In a weighted directed graph the run scans, from u, only the arcs (u, x) out of u. Theorems 1 to 3 hold as stated with directed paths, since each proof follows a path forward from its start: the step from x to y on P is an arc (x, y), scanned from x. A run from s gives distances from s, not to s (Example 5).

Unweighted graphs. Give every edge weight 1. Then d_w = d, every label is a layer number, and by Exercise 6 the run settles all of layer 0, then layer 1, and so on. This is the layer method of Walks, paths, cycles and connected graphs, grown one vertex at a time.

Negative weights. With a negative weight the proof of Theorem 1 breaks at its one use of w \ge 0, and the answers can be wrong (Example 6). The Bellman-Ford method, which passes over every edge v - 1 times, handles negative weights when no closed walk weighs less than 0; it is not taken up here.

Counting the work. For v vertices and e edges there are at most v rounds. Finding the least label looks at each unsettled label once, at most \displaystyle v + (v - 1) + \cdots + 1 = \frac{v(v+1)}{2} looks in all. Scanning u checks each edge at u, and each vertex is scanned once, so the checks total the sum of the degrees, 2e, by the handshake count of Degree, the handshake lemma and complete graphs. Since \displaystyle e \le \frac{v(v-1)}{2}, the work is at most about \displaystyle \frac{3}{2}v^2: it grows like v^2, while the number of paths can grow like (v - 2)!.

Worked examples

Boundaries

• Weights \ge 0. Zero weights are fine (Example 3); one negative weight can give wrong answers (Example 6).
• One start. A run gives distances from s only. In a directed graph the distances to s can be different (Example 5), and all pairs need a run from every vertex.
• Ties. Distances do not depend on how ties are broken; the predecessors and the tree can (Example 2).
• Reach. Vertices that cannot be reached from s keep the label \infty and are never settled.

Where this goes next

Spanning trees and minimum spanning trees asks for the cheapest network rather than the cheapest route, and one of its methods also grows a tree from a single vertex, but adds the cheapest single edge each round instead of the cheapest total route. Negative weights call for the Bellman-Ford method.

Exercises

Day 1: running the method

1. Run the method from E in Figure 1. Give every distance, predecessor and the order of settling, and name any town with two cheapest routes from E.
2. Run the method from M in Figure 2. Check that d_w(M, G) agrees with Example 2.
3. The table gives the price in dollars of a direct freight leg between five ports. Run the method from P and give the cheapest route to T.

4. In Exercise 3 only the price from P to S is wanted. After which round may the run stop, and what allows it? Which vertex is unsettled then, and is its label already its distance?
5. Stops G and M of Figure 2 both have rail yards. For each stop, find the nearer yard and the time to it.

Day 1: reasoning

6. With all weights \ge 0, prove that the labels of the vertices, at the moment each is settled, never decrease from one round to the next.
7. Prove that a run settles exactly the vertices that can be reached from s, and that every other vertex keeps the label \infty.

Day 2: trees, directions and layers

8. Give the shortest-path tree from P in Exercise 3 and its total weight, and check that it is a tree.
9. In Example 2, find every shortest-path tree from G, that is, every tree whose path from G to each stop is a fastest route.
10. Run the method from W in Figure 4.
11. Every edge of the graph on \{1, \ldots, 7\} with edges 12, 13, 24, 34, 35, 46, 57, 67 has weight 1. Run the method from 1, breaking ties by the smaller number. Give the labels and the tree, and compare the labels with the layers from 1.

Day 2: negative weights and counting

12. A directed graph has arcs (s, x) of weight 4, (s, y) of 6, (y, x) of -3, (x, z) of 3 and (s, z) of 8. Run the method from s and compare with the true distances.
13. A road network has 2{,}000 vertices and 5{,}000 edges. Bound the looks and the checks of a run, counted as in the procedure.
14. In K_6, how many paths join two given vertices?

Day 2: reasoning

15. With all weights positive, prove that a vertex x lies on some cheapest path from s to t if and only if d_w(s, t) = d_w(s, x) + d_w(x, t).
16. Refute with a counterexample: “in a shortest-path tree from s, the path between any two vertices is a cheapest path between them.”
17. In a directed graph no arc enters s, the arcs out of s may have negative weights, and all other arcs have weights \ge 0. Prove that a run from s still gives every distance from s.