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{cases}\min\{w(p):s\rightsquigarrow v\}&\text{if a path exists}\\\infty&\text{if }v\text{ is unreachable}\\-\infty&\text{if a negative-weight cycle lies on some }s\rightsquigarrow v\text{ path.}\end{cases}$$ 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$?* $$\textbf{if } v.d > u.d + w(u,v):\quad 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\rightsquigarrow 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 $\langle v_0,\dots,v_k\rangle$ 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.