Relaxation and the Optimality Condition Behind Shortest-Path Algorithms

The heap-driven routine inside a map service, the round-based routine inside a routing daemon, and the triple loop inside a network-analysis library all perform the same primitive operation on the same kind of data. What separates them is not the update rule but the order in which the updates are applied. Understanding that separation explains why some of them tolerate negative edge weights and others do not, and why the ones that tolerate negative weights can still be defeated by a graph that has no answer at all.

What counts as a path

Fix a directed graph $G = (V, E)$ with an edge weight $w(u,v)$ for each edge. Weights may be negative. A path from $s$ to $v$ is a sequence of vertices $s = v_0, v_1, \dots, v_k = v$ where each consecutive pair is an edge; its weight is the sum of the edge weights. The shortest-path distance is

$$\delta(s,v) = \min {, w(p) : p \text{ is a path from } s \text{ to } v ,},$$

with $\delta(s,v) = \infty$ when no path exists.

Whether repetition is allowed matters more than it first appears. If walks that revisit vertices were permitted without restriction, a reachable cycle of negative total weight would let a walk descend without limit, and $\delta$ would be $-\infty$. The standard formulation therefore asks for simple paths. When no negative cycle is reachable from $s$, the two formulations agree: any cycle in a walk has weight at least zero, so deleting it cannot increase the walk’s weight, and a minimum-weight walk can always be reduced to a simple one. That reduction is the reason a shortest path, when it exists, can be assumed to contain at most $|V| - 1$ edges, a fact that later fixes the iteration count of the round-based algorithm described in Bellman-Ford, Round Counts, and Negative-Cycle Detection.

The optimal-substructure property follows from the same argument. If $p$ is a shortest path from $s$ to $v$ and $u$ is a vertex on $p$, then the prefix of $p$ ending at $u$ is a shortest path from $s$ to $u$. Suppose it were not: some cheaper path $q$ from $s$ to $u$ exists, and splicing $q$ onto the remainder of $p$ yields a path to $v$ cheaper than $p$, contradicting $p$‘s minimality. This is a cut-and-paste argument, and it is the only structural fact the algorithms need.

Relaxation as an upper-bound update

Each vertex carries a tentative distance $d[v]$, initialised to $\infty$ except $d[s] = 0$, and a predecessor pointer used later to reconstruct the path. Relaxing an edge $(u,v)$ tests whether the best known route to $u$, extended by that edge, beats the best known route to $v$:

$$d[v] \leftarrow \min(d[v],; d[u] + w(u,v)).$$

Two invariants hold from the first operation onward. First, $d[v] \ge \delta(s,v)$ for every vertex: a tentative label always corresponds to some real path, so it can never be smaller than the optimum. Second, if $d[u] = \delta(s,u)$ at the moment $(u,v)$ is relaxed, then afterwards $d[v] = \delta(s,v)$, because the cheapest path to $v$ that ends with $(u,v)$ has just been considered. The predecessor pointer records the edge that produced the current label, so the pointers form a tree rooted at $s$ as long as no vertex is improved twice through a cycle.

The C fragment below is the whole primitive. The first guard is not cosmetic: in two’s-complement arithmetic, adding a weight to the sentinel for an unreachable vertex produces a finite value that would be accepted as a genuine improvement. The second guard covers the other end of the range, where a large finite label plus a positive weight wraps below zero and looks like a better route.

/* dist[] holds INT64_MAX for unreachable vertices; dist[s] = 0. */
static int relax(int64_t *dist, int *parent, int u, int v, int64_t w)
{
    if (dist[u] == INT64_MAX)            /* u is still unreachable */
        return 0;
    if (w > 0 && dist[u] > INT64_MAX - w) /* d[u] + w would overflow */
        return 0;
    if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        return 1;                         /* label improved */
    }
    return 0;
}

Sixty-four-bit labels are the practical default because a path of a thousand edges with weights around $10^{7}$ already exceeds the range of a signed 32-bit integer, and a silently wrapped distance is indistinguishable from a correct one at the call site.

Why the schedule is the algorithm

Every correct method can be described as: relax edges until nothing changes. The differences are entirely in which edge is relaxed when. A schedule is valid for a source $s$ if, for every vertex $v$ reachable from $s$, some shortest path from $s$ to $v$ has its edges relaxed in path order, meaning the prefix edge before the edge that follows it, at least once.

Under that condition the labels converge to $\delta$. The argument is an induction on the number of edges in the chosen shortest path. The base case is the source. For the step, assume the prefix of length $k$ has been relaxed in order and $d[u] = \delta(s,u)$ at the time the $k$-th edge is relaxed; the update then sets $d[v] = \delta(s,v)$, and no later relaxation can raise a label.

Two schedules dominate. Dijkstra’s algorithm settles vertices in nondecreasing order of tentative label and relaxes each outgoing edge once, which makes it valid whenever weights are nonnegative: the vertex with the smallest label must already be optimal, because every route to it would have to pass through a vertex whose label is no smaller. Bellman-Ford instead relaxes every edge $|V| - 1$ times in arbitrary order, which is valid for any graph without a reachable negative cycle, because after round $k$ every shortest path of at most $k$ edges has been relaxed in order. The first schedule is faster and narrower; the second is slower and general. Dijkstra and the Settled Set works through the exchange argument that justifies the narrower one.

Label-correcting methods, which maintain a queue of vertices whose labels changed, sit between the two: they are Bellman-Ford with a heuristic schedule, and they inherit Bellman-Ford’s worst case.

The fixed point

Suppose the process halts with no edge relaxable. Then for every edge $(u,v)$ with $d[u]$ finite, $d[v] \le d[u] + w(u,v)$. Take any vertex $v$ reachable from $s$ and a shortest path $s = v_0, \dots, v_k = v$. Applying the inequality along the path gives

$$d[v] \le d[v_0] + \sum_{i=1}^{k} w(v_{i-1}, v_i) = 0 + \delta(s,v).$$

Combined with the upper-bound invariant, $d[v] = \delta(s,v)$. So a fixed point is not merely stable, it is correct, provided a fixed point is reached. The condition $d[v] \le d[u] + w(u,v)$ is the discrete analogue of the Bellman optimality equation, and every algorithm in this family is a monotone decrease toward it.

When the answer is minus infinity

If a negative cycle is reachable from $s$, no fixed point exists. Relaxing the cycle’s edges in order lowers the label of its entry vertex by the cycle’s total weight, and repeating that lowers it again, so the process diverges. Two consequences follow for implementation. First, a loop that terminates only when a full pass makes no change will not terminate. Second, a loop bounded by a round count terminates but produces meaningless labels, so the bound has to be paired with a detection step: if the final pass still improves something, a reachable negative cycle exists.

Detection is not the same as localisation. The vertices whose labels improved on the extra pass need not lie on the cycle itself; they are merely reachable from it. Walking predecessor pointers from such a vertex for $|V|$ steps must revisit a vertex, and the segment between the two visits is a negative cycle. This distinction matters when the goal is to report the offending cycle rather than to report its existence.

The same divergence appears in an undirected graph with a single negative edge. Traversing that edge and returning along it is a cycle of negative weight, so an undirected graph with any negative edge has no finite shortest paths across that edge. Undirected instances are therefore restricted to nonnegative weights, which is why implementations that accept an undirected flag typically reject negative input outright.

What the relaxation account does not cover

The relaxation account says nothing about performance, and the performance differences are severe. A valid schedule can be quadratic in the number of relaxations and still be correct; the choice among valid schedules is where the engineering lives. It also does not extend to constraints that couple paths together, such as a path that must avoid a set of vertices or a pair of paths that must be disjoint, because the optimal-substructure argument fails once the subproblem has to remember what the prefix used. Those become problems over expanded state spaces rather than over the original graph, of the kind handled by Resource-Constrained Shortest Paths and Label-Setting with Dominance.

What survives is the accounting: any algorithm in this family can be checked by asking whether its schedule is valid, and any implementation can be checked by asking whether its labels are upper bounds that satisfy the fixed-point inequality at termination. Both questions are cheap to test and catch most of the bugs that shortest-path code actually contains.