8.23

Idea. If every optimal u-v path uses at most k edges, it is enough to run Bellman–Ford for k iterations instead of the usual n−1. One relaxation sweep over all m edges costs Θ(n+m) (the vertices are scanned once for initialisation and the edges once for relaxation), so k sweeps give O(k·(n+m)) time.

Algorithm.

Input : graph G = (V,E,w), vertices u,v, edge bound k dist[x] ← +∞ for x ∈ V pred[x] ← NIL dist[u] ← 0 for i = 1 .. k do ── k iterations updated ← false for each edge (a,b) with weight w(a,b) do if dist[a] + w(a,b) < dist[b] then dist[b] ← dist[a] + w(a,b) pred[b] ← a updated ← true if not updated then break ── early stop if no change return dist[v] and the path obtained by following pred[] from v back to u

Correctness sketch.
Let P be an optimal u-v path with at most k edges. After the first iteration every vertex reachable from u by ≤1 edge has its exact distance; by induction, after i iterations every vertex reachable by ≤i edges is correctly labelled. Thus after k iterations v has its true shortest-path distance. Relaxations never increase distances, so the final labels are optimal.

Complexity. Each pass scans |V| distances and |E| edges once, costing Θ(n+m). Performing at most k passes gives Θ(k·(n+m)). The predecessor array allows the path to be rebuilt in O(k) additional time and space.

Back to Chapter 8