Shortest paths: the relaxation framework

The single-source shortest-paths problem

Given a weighted directed graph $G=(V,E)$ and a source $s$, find a minimum-weight path from $s$ to every vertex. The shortest-path weight is $$\delta (s,v)=\{\begin{array}{ll}\min \{w(p):s⇝v\}& \text{if a path exists}\\ \infty & \text{if }v\text{ is unreachable}\\ -\infty & \text{if a negative-weight cycle lies on some }s⇝v\text{ path.}\end{array}$$ The third case matters: if you can loop through a negative cycle on the way to $v$, you can make the path arbitrarily cheap, so $\delta$ is $-\infty$.

The two primitives

Every algorithm in this and the next two lessons is built from exactly two operations. Each vertex carries v.d (a shortest-path estimate — an upper bound on $\delta (s,v)$) and v.π (its predecessor).

INITIALIZE-SINGLE-SOURCE(G, s): set v.d = ∞, v.π = NIL for every vertex, then s.d = 0.

RELAX(u, v, w): can we reach $v$ more cheaply by going through $u$? $$\text{if }v.d>u.d+w(u,v):v.d=u.d+w(u,v),v.\pi =u.$$

That is the whole toolkit. Bellman-Ford, DAG-shortest-paths, and Dijkstra differ only in the order and number of times they relax edges.

Worked example of relaxation

Suppose u.d = 5, w(u,v) = 2, and v.d = 10. Then u.d + w(u,v) = 7 < 10, so RELAX sets v.d = 7 and v.π = u. If instead v.d were already 6, then $6\le 7$ and RELAX does nothing — estimates only ever decrease.

The properties that make it all work

• Upper-bound: v.d ≥ δ(s,v) always, and once v.d = δ(s,v) it never changes again.
• Triangle inequality: $\delta (s,v)\le \delta (s,u)+w(u,v)$.
• Convergence: if $s⇝u\to v$ is a shortest path and u.d = δ(s,u) before RELAX(u,v,w), then v.d = δ(s,v) after it.
• Path-relaxation: if you relax the edges of a shortest path $⟨v_0,\dots ,v_k⟩$ in order — even with arbitrary other relaxations mixed in between — then v_k.d = δ(s,v_k).

The path-relaxation property is the linchpin of Bellman-Ford's correctness: after $i$ passes over all edges, every shortest path of $\le i$ edges has its correct value.