Shortest-path optimality and potentials
Certify shortest distances with feasible labels, understand Dijkstra's nonnegative-weight assumption, and reweight edges without changing path order.
On this page
The question for today
What you’ll understand
- Check a shortest-path certificate using edge inequalities and attained path lengths.
- Locate the nonnegative-weight assumption in Dijkstra's settling argument.
- Derive endpoint telescoping for a potential reweighting.
Finding a short route is easy; proving that no shorter route exists is the interesting part. A shortest-path certificate combines two inequalities: an actual route gives an upper bound on the optimum, while carefully chosen vertex labels give a lower bound on every route. Potentials organize those labels and can transform edge weights without changing which source-to-destination route wins. The same algebra explains both a useful proof technique and the danger of settling vertices too early.
Paths provide upper bounds, labels provide lower bounds
Work with a finite directed graph and real edge weights. For vertices reachable from a source s, assume no negative-weight cycle is reachable from s, so finite shortest distances exist. A path with cost L proves the shortest distance is at most L. Now give reachable vertices labels h with h(s) = 0 and h(v) ≤ h(u) + w(u,v) on every reachable edge. Summing along any source-to-v path makes intermediate labels cancel, proving h(v) is at most every such path's cost.
If each label is also attained by an explicit source path, its lower and upper bounds meet and the labels are exact distances. Both parts matter. All-zero labels satisfy the edge inequalities when weights are nonnegative but usually underestimate distances. A spanning collection of paths gives attainable labels but can overestimate if a better edge was ignored. A reachable negative cycle prevents a finite feasible labeling: summing its edge inequalities would force zero to be at most a negative total weight.
Why the nearest unsettled vertex is safe
Dijkstra's algorithm maintains tentative lengths of discovered source paths and repeatedly settles an unsettled vertex of smallest tentative length. With nonnegative edge weights, consider the first edge on a shortest route that leaves the settled set. Its preceding settled vertex already has the correct distance, so relaxation offers a tentative length no larger than the whole route to any later vertex. Nonnegative remaining edges make that comparison valid. The smallest tentative choice therefore cannot conceal a strictly shorter route through unsettled vertices.
A negative edge breaks the last comparison even without a negative cycle. For example, direct edges s to a of cost two and s to b of cost five, followed by b to a of cost minus four, give a true distance to a of one. Settling a at two before processing b is premature. Bellman–Ford instead repeatedly relaxes all edges; with no reachable negative cycle, shortest simple paths use at most |V| minus one edges, giving a finite bound on needed passes. Including initialization, its arithmetic/comparison work is O(|V||E| + |V|) in the standard unit-cost model.
Reweight once, preserve every relevant comparison
A potential is any vertex function used in the reweighting formula. To guarantee nonnegative reweighted edges, it must satisfy the feasible-label inequalities. Johnson's all-pairs construction adds a new source with zero-weight edges to every vertex, obtains potentials from Bellman–Ford, and then runs Dijkstra on the reweighted graph if no negative cycle exists. The extra source makes every vertex reachable for the potential computation. Correcting the endpoint offset recovers original distances without changing any winning path.
Reweighting does not erase a negative cycle: the endpoint corrections around a closed walk cancel completely. It also does not authorize arbitrary label rounding, because a small numerical violation can make an edge unexpectedly negative. With integer or rational input, exact arithmetic and bit lengths require explicit treatment beyond a count of relaxations. For unreachable destinations, use a separate infinity convention rather than inserting infinity into subtraction formulas. These boundaries keep a beautiful telescoping identity connected to a sound algorithm.
Work it through
Check and reweight a small distance certificate
The directed edges are s→a of weight 4, s→b of weight 5, a→b of weight −2, and b→t of weight 3. Check labels h(s)=0, h(a)=4, h(b)=2, h(t)=5 and compute the reweighted edges.
The labels are attained by the paths s, s→a, s→a→b, and s→a→b→t. Their costs are respectively zero, four, two, and five.
Check all edge inequalities: 4 ≤ 0+4, 2 ≤ 0+5, 2 ≤ 4−2, and 5 ≤ 2+3. Therefore every source path has cost at least its destination label, proving these attained labels are shortest distances.
Reweighting gives 0 for s→a, 3 for s→b, 0 for a→b, and 0 for b→t. The preferred s-to-t route now has cost zero; adding h(t)−h(s)=5 recovers its original cost.
All reweighted edges are nonnegative, and the original shortest s-to-t distance is five. The alternative route s→b→t costs eight originally and three after reweighting, preserving the difference.
The living notebook
Explore the model
Interactive lab · modular
A walk can revisit a vertex after its shortest arrival
Pause and reset, then set both controls to modulus 6 and additive step 1. Interpret each displayed addition as a unit-cost directed edge on the six-cycle. Predict first arrival at residue 4 after four edges and another arrival after ten; Step through the first cycle and compare elapsed edge counts. For a fresh comparison, pause and reset, then set modulus 6 and step 2: residue 4 is reached after two edges and odd residues are unreachable. The model displays this deterministic walk, not Dijkstra, weighted-edge relaxation, or arbitrary potentials.
- Residue r0
- 0
- Orbit period · m/gcd(m,a)
- 12
- Distinct residues visited
- 1 of 12
Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA vertex's first attainable path can be certified only against the graph's actual alternatives; repeated walks need not be shortest.
Pause & reason
Check your understanding
Your turn
Try it yourself
For edges s→a of weight 3, a→t of weight −1, and s→t of weight 5, verify potentials h(s)=0, h(a)=3, h(t)=2. Reweight the edges and recover the original shortest distance from the new one.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Check both the edge inequalities and an attaining source path before calling the labels exact.
Compare with the solution
The inequalities are 3 ≤ 3, 2 ≤ 3−1, and 2 ≤ 5, all valid. The paths s→a and s→a→t attain labels three and two. Reweighting yields costs 0,0,3 respectively, so the shortest reweighted route to t has cost zero. The original distance is zero − h(s) + h(t) = 2. The direct edge remains three units more expensive in both descriptions. This example has a negative edge but no cycle, so finite shortest paths and feasible potentials are consistent.
Keep the idea
Take it with you
- Attained path lengths and feasible label inequalities together certify optimality.
- Dijkstra's settling proof relies on nonnegative edge weights.
- Potential corrections preserve endpoint-to-endpoint path ordering and preserve every cycle weight.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.