8.2 Shortest paths
To find a shortest path from node \(s\) to node \(t\) with arc lengths \(c_{ij}\), send one unit of flow from \(s\) to \(t\) at least cost: \(b_s = 1\), \(b_t = -1\), other \(b_i = 0\). By Theorem 8.1.1 the optimal flow is \(0\) or \(1\) on each arc and traces a path. The dual has a variable \(\pi _i\) for each node, the potential, and reads: maximise \(\pi _s - \pi _t\) subject to \(\pi _i - \pi _j \leq c_{ij}\) for every arc. With \(d_i = \pi _s - \pi _i\), the distances from \(s\) satisfy Bellman’s equations \(d_j = \min _i(d_i + c_{ij})\), the principle of optimality of dynamic programming: the last arc of a shortest path to \(j\) comes from a shortest path to its tail.
When all lengths are non-negative, Dijkstra’s algorithm (1959) computes the distances from \(s\) to every node: keep a set \(P\) of nodes whose distances are final, starting with \(P = \{s\}\), \(d_s = 0\); repeatedly add the node outside \(P\) with the smallest tentative label \(d_j = \min _{i \in P}(d_i + c_{ij})\), and update the labels of its neighbours.
Theorem 8.2.1 (Dijkstra). If all \(c_{ij} \geq 0\), the label of each node is its true distance from \(s\) when the node is added to \(P\).
Proof. By induction on \(|P|\). Let \(j\) be the next node added, with label \(d_j\), which is the length of some path from \(s\). Any path from \(s\) to \(j\) leaves \(P\) at some arc \((i, k)\) with \(i \in P\), \(k \notin P\); its length is at least \(d_i + c_{ik}\) (by the induction hypothesis for \(i\), and since the remaining arcs have non-negative length), which is at least the label of \(k\), which is at least \(d_j\) by the choice of \(j\). So no path is shorter than \(d_j\). □
With a heap the algorithm runs in \(O(m\log n)\) time on a network with \(m\) arcs. With negative lengths it can fail (Problem 8.7.1); the Bellman–Ford algorithm handles them, and detects negative cycles, in \(O(mn)\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.