Edge Relaxation And Distance Inequalities

Why Relax an Edge?

A shortest-path computation rarely knows every distance at the start. Instead, it stores a tentative label for each vertex and improves those labels when it finds a cheaper route. The basic operation is local: inspect one weighted edge and ask whether reaching its tail, then crossing that edge, gives a better route to its head. The shortest-path triangle inequality explains why this is the right comparison.

Throughout, a weighted directed graph is a finite directed graph whose arcs have real weights \(w(u,v)\). A directed path has cost equal to the sum of its arc weights. Fix a source vertex \(s\). Write \(\delta(v)\) for the minimum cost of a directed path from \(s\) to \(v\), and set \(\delta(v)=\infty\) if no such path exists. We assume that no negative-weight directed cycle is reachable from \(s\), so every reachable vertex has a finite shortest-path distance. We use \(\infty+a=\infty\) for finite \(a\).

The common initialization is \(d[s]=0\) and \(d[v]=\infty\) for \(v\ne s\). A finite label obtained by relaxation is the cost of a route found so far, so it is an upper bound on the true shortest-path distance. A predecessor pointer records the tail of the arc used for the latest strict improvement to that label. It is information about the update, not a claim that the whole shortest path has already been finalized.

The Distance Inequality

Proof. Since \(u\) is reachable and there is an arc from \(u\) to \(v\), appending that arc to a path from \(s\) to \(u\) gives a route from \(s\) to \(v\). Take a shortest path to \(u\), whose cost is \(\delta(u)\). Appending \(u\to v\) gives a route of cost \(\delta(u)+w(u,v)\). If this route repeats a vertex, the repeated section is a closed directed walk. Under the assumption that no negative cycle is reachable from \(s\), such a section cannot have negative cost: a negative closed walk contains a negative directed cycle, as can be seen by splitting it at repeated vertices until cycles remain. Removing a nonnegative closed section gives a path of no greater cost. Thus there is a path to \(v\) of cost at most \(\delta(u)+w(u,v)\), and the minimum path cost satisfies the stated inequality. \(\square\)

This is the shortest-path version of a triangle inequality: going to \(u\) and then taking one more arc cannot be cheaper than the best route to \(v\). Relaxation tests whether the current labels have yet recorded that particular route. If \(d[u]\) is a route cost to \(u\), then \(d[u]+w(u,v)\) is a route cost to \(v\). A strict improvement replaces the old route estimate by a cheaper one.

The inequality is one-sided. It does not say that every arc must give the best route to its head, nor that a tentative label is already the true distance. Equality has a useful interpretation: if a shortest path to \(v\) ends with the arc \(u\to v\), then its prefix to \(u\) must itself be shortest. Otherwise, replacing that prefix by a cheaper path to \(u\) would produce a cheaper path to \(v\). In that case, \(\delta(v)=\delta(u)+w(u,v)\); the arc is called tight with respect to these distances.

What a Relaxation Guarantees

Proof. Let the relaxed arc be \(u\to v\). If \(d[u]=\infty\), no update is made. If \(d[u]\) is finite, it is the cost of a route to \(u\) by hypothesis. Appending \(u\to v\) gives a route to \(v\) of cost \(d[u]+w(u,v)\). If this candidate is strictly smaller than \(d[v]\), the new label is exactly that route cost, so the property is preserved. The update makes \(d[v]\) smaller. If the candidate is not strictly smaller, no label changes. All other labels are unaffected. Therefore labels never increase, and every changed label strictly decreases. \(\square\)

This proposition justifies the safety of a single update, even when some edge weights are negative. It does not say that one pass over the edges finds all shortest paths. In particular, the triangle inequality concerns true distances, whereas a relaxation compares current tentative labels. The order and number of relaxations matter to whether all improvements have been found.

When Labels Match Distances

A collection of labels can be checked using all the arcs. The following result gives a precise condition under which those local checks certify the distances. The route-witness condition matters: inequalities alone can certify lower bounds but cannot rule out labels that are too large.

Proof. Fix a reachable vertex \(v\). Because \(d[v]\) is the cost of a path from \(s\) to \(v\), the minimum path cost satisfies \(\delta(v)\leq d[v]\). For the reverse inequality, take any path \(s=v_0,v_1,\ldots,v_k=v\). Starting with \(d[v_0]=d[s]=0\), apply the assumed arc inequality to each arc in order: \(d[v_i]\leq d[v_{i-1}]+w(v_{i-1},v_i)\) for \(1\leq i\leq k\). Repeated substitution gives \(d[v]\leq \sum_{i=1}^{k}w(v_{i-1},v_i)\), the cost of this path. This holds for every path from \(s\) to \(v\), so \(d[v]\leq\delta(v)\), since \(\delta(v)\) is the minimum of their costs. Combining both inequalities yields \(d[v]=\delta(v)\). \(\square\)

In this proposition, each edge inequality says that the label at the head is no greater than the route obtained through the tail. When an edge violates that inequality, relaxing it can repair the violation if the tail label is finite. A single relaxation checks just one edge; checking all edges is a broader consistency test.

Negative Weights and the Scope of Relaxation

The relaxation rule itself does not require nonnegative weights. It compares two route costs, and a negative edge can produce a valid strict improvement just as a positive edge can. What matters for the distance interpretation here is that the graph has no negative cycle reachable from the source. If such a cycle exists, repeatedly going around it can make route costs arbitrarily small, so there is no finite shortest-path distance for vertices reachable from that cycle.

Common Pitfalls

Using the head label in the candidate. For an arc \(u\to v\), the candidate is \(d[u]+w(u,v)\), not \(d[v]+w(u,v)\). For example, in the first worked example, when \(d[a]=3\) and the weight of \(a\to b\) is \(2\), the correct candidate is \(3+2=5\), which improves \(d[b]=8\). Using the head label would give \(8+2=10\), incorrectly missing the improvement.

Updating on equality. The rule uses a strict comparison. If a candidate equals the current label, it gives another route of the same cost, not a better distance. Updating on equality is unnecessary and may change a predecessor pointer without improving the label.

Confusing a local check with a completed computation. The triangle inequality holds for true distances on every arc leaving a reachable vertex. But processing an arc once only compares the labels available at that moment. A later decrease at its tail may create a better candidate, as the negative-edge example illustrates. Relaxation defines the local update; by itself, it does not specify a complete shortest-path algorithm or promise that a particular sequence of updates is sufficient.