Edge Relaxation and Optimal Substructure

A single-source shortest-paths algorithm maintains, for every vertex $v$, an estimate $d[v]$ of the true shortest-path distance $\delta(s,v)$ from the source $s$, together with a predecessor pointer $\pi[v]$ used to reconstruct the path. Initially $d[s] = 0$ and $d[v] = \infty$ for every other vertex, reflecting total ignorance. The relax operation takes one directed edge $(u,v)$ with weight $w(u,v)$ and asks a single question: is the path to $u$ plus this edge better than what we currently believe about $v$? If $d[u] + w(u,v) < d[v]$, then $v$'s estimate is genuinely improvable, so we set $d[v] \leftarrow d[u] + w(u,v)$ and $\pi[v] \leftarrow u$. Otherwise the edge tells us nothing new, and we do nothing. This tiny operation is the only place where any SSSP algorithm actually changes its answer. Dijkstra's algorithm relaxes edges in an order dictated by a priority queue keyed on current distance; Bellman-Ford relaxes every edge, every round, for $|V|-1$ rounds, tolerating negative weights that would break Dijkstra; the DAG algorithm relaxes edges in one pass, following a topological order that guarantees every predecessor is finalized before it is used. All three are the same recurrence executed with different scheduling discipline. This uniformity is why relaxation deserves its own treatment: master it once, and three algorithms' correctness proofs become the same three lines repeated. The mathematical backbone is optimal substructure: a shortest path from $s$ to $v$ is composed of a shortest path from $s$ to some predecessor $u$, followed by the single edge $(u,v)$. If a shortest $s\to v$ path had a suboptimal sub-path, you could splice in a shorter sub-path and get a shorter $s\to v$ path, a contradiction (this "cut and paste" argument is identical in spirit to the one used for Dynamic Programming optimality proofs). Because shortest paths decompose this way, computing $\delta(s,v)$ reduces to knowing $\delta(s,u)$ for predecessors $u$ and taking a minimum over one addition each — precisely what relax computes, one candidate edge at a time.

Relaxation itself is a three-line primitive, but its correctness rests on two supporting facts that every SSSP algorithm depends on implicitly.

The triangle inequality for shortest-path estimates. For any edge $(u,v)$, the true distances satisfy

This is just the statement that going directly can never be worse than detouring — if it were, the "direct" shortest path from $u$ to $v$ used as a shortcut would contradict $\delta(s,v)$ being shortest. Relaxation is designed to enforce this inequality on the estimates $d$: whenever it is violated ($d[u]+w(u,v) < d[v]$), relax repairs it by lowering $d[v]$.

The upper-bound invariant. At every point in every correct SSSP algorithm, $d[v] \ge \delta(s,v)$ for all $v$, and equality is reached once enough relaxations have occurred along a shortest path. Estimates start at $\infty$ (a safe overestimate) and only ever decrease, never below the truth, because relax only ever assigns $d[u] + w(u,v)$, a length of an actual walk from $s$ to $v$ — and no actual walk can be shorter than the shortest path.

The convergence property ties these together: if $s \to u_1 \to u_2 \to \cdots \to v$ is a shortest path and the edges $(s,u_1), (u_1,u_2), \ldots, (u_k,v)$ are relaxed in that order (not necessarily consecutively — other relaxations may be interleaved), then after the last of these relaxations, $d[v] = \delta(s,v)$ exactly. This is the theorem that licenses every SSSP algorithm: as long as an algorithm's schedule relaxes every shortest path's edges in path order at some point in its execution, it computes correct distances. ```pseudocode // Shared initialization used by every SSSP algorithm INITIALIZE-SINGLE-SOURCE(G, s): for each vertex v in G.V: d[v] = ∞ pi[v] = NIL d[s] = 0 // The one operation every SSSP algorithm calls repeatedly RELAX(u, v, w): if d[u] + w(u, v) < d[v]: d[v] = d[u] + w(u, v) pi[v] = u return true // an improvement happened return false // edge told us nothing new // Generic scheduler: differs per algorithm only in which edges, // in what order, and how many times GENERIC-SSSP(G, s, edge_schedule): INITIALIZE-SINGLE-SOURCE(G, s) for (u, v) in edge_schedule: // schedule defines the algorithm RELAX(u, v, w(u, v)) return d, pi ``` The three downstream algorithms instantiate `edge_schedule` differently:

• DAG shortest paths: process vertices in topological order, relaxing all outgoing edges of each — one pass suffices because a topological order guarantees predecessors are already finalized.
• Bellman-Ford: relax every edge, $|V| - 1$ times, in any fixed order — enough rounds for the worst-case shortest path (which has at most $|V|-1$ edges) to have its edges relaxed in order at least once.
• Dijkstra: relax edges out of the vertex with currently-smallest $d$ value, greedily, using a priority queue — correct only when all weights are non-negative, because the greedy choice assumes no future relaxation could ever lower an already-finalized vertex's distance.

Cost of relaxation itself. A single call to `RELAX` does one addition and one comparison, so it is $O(1)$. Every SSSP algorithm's total running time is therefore dominated by how many times relax is called and what bookkeeping surrounds each call (e.g., a priority-queue decrease-key operation in Dijkstra). Concretely:

• DAG shortest paths: each edge relaxed exactly once, giving $O(V+E)$ total (topological sort is also $O(V+E)$).
• Bellman-Ford: every edge relaxed in every one of $|V|-1$ rounds, giving $O(VE)$.
• Dijkstra with a binary heap: each edge relaxed once, but each successful relaxation triggers a $O(\log V)$ decrease-key, giving $O((V+E)\log V)$.

The pattern is always: (number of relax calls) × (cost per call including auxiliary structure). This decomposition is why relaxation is worth studying in isolation — it is the fixed, cheap part; the variable, algorithm-defining part is the schedule.

Correctness — the upper-bound property. Claim: at all times during any execution that starts from `INITIALIZE-SINGLE-SOURCE` and calls `RELAX` zero or more times (in any order, on any edges), $d[v] \ge \delta(s,v)$ for every vertex $v$, and this holds with equality once no more relaxations can improve $d[v]$. Proof by induction on the number of relax calls. Base case: after initialization, $d[s]=0=\delta(s,s)$ and $d[v]=\infty \ge \delta(s,v)$ for all other $v$, since $\infty$ dominates any finite distance. Inductive step: suppose the invariant holds before a call `RELAX(u,v,w)`. If the call does nothing, the invariant is preserved trivially. If it updates $d[v] \leftarrow d[u]+w(u,v)$, then by the inductive hypothesis $d[u] \ge \delta(s,u)$, so

the last step being exactly the triangle inequality for true distances. So the invariant is preserved. $\blacksquare$

Correctness — the convergence property. Claim: let $p = \langle s=v_0, v_1, \ldots, v_k=v\rangle$ be any shortest path from $s$ to $v$. If the edges $(v_0,v_1), (v_1,v_2), \ldots, (v_{k-1},v_k)$ are relaxed, in that left-to-right order, at some (possibly non-consecutive) points during an execution, then $d[v] = \delta(s,v)$ holds immediately after the last of these relaxations, and continues to hold forever after (by the upper-bound property, $d$ never increases below the true distance and never needs to decrease again below $\delta(s,v)$ once it has hit it). Proof sketch by induction on $i$, showing $d[v_i] = \delta(s,v_i)$ right after $(v_{i-1},v_i)$ is relaxed. Base case $i=0$: $d[v_0]=d[s]=0=\delta(s,s)$ from initialization, and this persists (by the upper-bound property, it can never go below $0$, and it starts there). Inductive step: assume $d[v_{i-1}] = \delta(s,v_{i-1})$ at the moment just before $(v_{i-1},v_i)$ is relaxed (this value cannot have changed since, because the upper-bound property says $d[v_{i-1}]$ never rises and it is already at its floor $\delta(s,v_{i-1})$, so any subsequent relaxation targeting $v_{i-1}$ would find no improvement). When $(v_{i-1}, v_i)$ is relaxed,

Because $p$ is a shortest path, $\delta(s,v_i) = \delta(s,v_{i-1}) + w(v_{i-1},v_i)$ exactly (this is the optimal-substructure fact: a sub-path of a shortest path is itself shortest). Combined with the upper-bound property ($d[v_i] \ge \delta(s,v_i)$ always), the relax call forces $d[v_i] = \delta(s,v_i)$. $\blacksquare$ This single theorem is the entire correctness argument reused by Dijkstra (whose greedy order happens to relax shortest-path edges in order thanks to non-negative weights), Bellman-Ford (whose brute-force $|V|-1$ full rounds guarantee every possible shortest path, which has at most $|V|-1$ edges, gets its edges relaxed in order at least once), and DAG-SSSP (whose topological order is by construction a valid path order for every path in the graph).

Honest tradeoffs. The generality of relaxation is also its limitation: it says nothing about how fast convergence happens — that is a scheduling question, answered differently (and with very different asymptotic costs) by each concrete algorithm. Relaxation also assumes edge weights compose additively and that "shorter" is well-defined, meaning negative-weight cycles break everything: if a cycle's total weight is negative, $\delta(s,v)$ is not even well-defined (you can loop forever, decreasing cost indefinitely), and relaxation will never converge — this is exactly the condition Bellman-Ford checks for with one extra pass.

Consider the small directed weighted graph with source $s$:

The true shortest distances are $\delta(s,s)=0$, $\delta(s,b)=1$, $\delta(s,a)=2$ (via $b$), $\delta(s,c)=4$ (via $b,a$), $\delta(s,d)=5$. Trace a schedule that is not Dijkstra's greedy order and not a topological pass — just some arbitrary sequence of relax calls — to show convergence does not depend on cleverness, only on eventually covering shortest-path edges in order.

After step 8, every $d[\cdot]$ equals the true $\delta(s,\cdot)$. Notice step 1 relaxed $(s,a)$ before the true shortest-path edges $(s,b)$ and $(b,a)$ had run, producing a temporarily wrong (too-large, per the upper-bound property) value $d[a]=4$; that's fine — the upper-bound property only guarantees $d[a]\ge \delta(s,a)$, never equality until the convergence property's specific ordering condition is met. Step 5 is where the shortest path's edges $(s,b),(b,a)$ have both now been relaxed in path order, so $d[a]$ locks to its true value $2$ and never changes again — exactly as the convergence proof predicts. Step 7 illustrates why order matters only up to sufficiency, not exclusivity: relaxing $(b,c)$ is harmless even though it doesn't help, because relax only ever improves or does nothing, never corrupts. This same trace, if scheduled as "process $s$, then $b$, then $a$, then $c$, then $d$" (a valid topological order for this DAG), would let a single forward pass compute everything correctly in exactly $|E|=6$ relax calls with zero wasted work — which is exactly the DAG-shortest-paths algorithm.

The relax operation and its convergence property emerged from work connecting graph shortest paths to dynamic programming and operations research in the 1950s, when digital computers first made large-scale network optimization tractable.

Every road-network routing engine — the kind behind consumer mapping applications — runs a heavily engineered variant of Dijkstra's algorithm (often combined with contraction hierarchies or A\*-style heuristics), but the correctness of every optimization layered on top still ultimately rests on the same relax invariant proven here. Internet routing protocols such as OSPF compute shortest paths internally using Dijkstra over link-cost graphs, again relying on relaxation converging correctly given non-negative costs. Compilers use relaxation-style dataflow fixpoint iteration (a direct generalization of Bellman-Ford's repeated-rounds idea) for reaching-definitions and other static analyses. Currency-arbitrage detection systems model exchange rates as edge weights via a logarithm transform and use Bellman-Ford specifically because it can detect the "negative cycle" that signals a profitable arbitrage loop. Any system that must combine local, pairwise cost information into a globally consistent set of optimal aggregate values — network delay estimation, project-scheduling critical paths, even certain reinforcement-learning value-iteration updates — is running some disciplined variant of edge relaxation under the hood.

:::quiz[What does a single call to RELAX(u, v, w) do when d[u] + w(u,v) is not less than d[v]?]

• It decreases d[v] anyway to keep estimates in sync
• It raises d[u] to match d[v]
• It leaves both d[v] and π[v] unchanged ✓
• It removes the edge (u,v) from consideration permanently

:::quiz[Which property guarantees that d[v] never becomes an underestimate of the true shortest distance δ(s,v)?]

• The greedy-choice property
• The upper-bound property (triangle-inequality invariant) ✓
• The optimal-substructure property alone
• The heap invariant

Ask the tutor: Can you show why the convergence property still holds even if unrelated edges are relaxed in between the shortest path's edges?