Relax every arc, as many rounds as there are nodes, and the labels settle. What they settle on is not just a list of distances: it is a feasible solution of the dual programme, πⱼ − πᵢ ≤ cᵢⱼ on every arc, and the tight arcs are the shortest routes. Because every constraint is a difference, adding a constant to every label changes nothing — which is what makes them prices. A negative cycle is the dual saying it has no feasible point at all.
Core ideas
The algorithm takes three lines. What it computes takes a lesson, because the labels are the dual and readers meet them as distances.
The dual constraint πⱼ − πᵢ ≤ cᵢⱼ involves only the difference of two labels, and so does the objective πₜ − πₛ. Add seven to every label and every constraint still holds and the objective is unchanged: the lab has a control that does exactly this and reports both facts. A distance from the source is one particular normalisation of a potential, chosen by setting πₛ = 0.
An arc with πⱼ − πᵢ = cᵢⱼ is tight. Complementary slackness says that flow can only travel on tight arcs, and that is exactly the statement that the shortest route uses tight arcs and no others. The lab draws the tight arcs heavily, so the shortest-path tree is visible as the subgraph where the dual constraint holds with equality.
Add the constraints round a cycle: the labels cancel completely and what is left is 0 ≤ (the cycle's total cost). A cycle of negative total cost therefore makes the dual infeasible, and by duality the primal is unbounded — go round the cycle forever and the cost falls forever. The relaxation detects it by still improving in a round it should not, and the lab names the cycle and prints what it costs.
The material
The dual first, then the relaxation that finds a feasible point of it, then the shift, then the case with no feasible point at all.
The shortest-path problem is already on this course: one unit supplied at the source, one demanded at the sink, and the costs read as lengths. What is new here is its dual, which is worth writing down because the labels every shortest-path algorithm computes turn out to be a feasible point of it.
A vector π, one number per node, is feasible for the shortest-path dual when πⱼ − πᵢ ≤ cᵢⱼ for every arc from i to j. The dual problem is to maximise πₜ − πₛ over all such vectors.
An arc is tight when the inequality holds with equality. The reduced cost of an arc is cᵢⱼ − (πⱼ − πᵢ), which is non-negative exactly when π is feasible.
The constraint says something plain: the price at the head may exceed the price at the tail by at most the cost of getting there. Any feasible π therefore has πₜ − πₛ at most the cost of every path from source to sink — add the constraints along the path and the intermediate terms cancel — so the dual objective is a lower bound on the shortest path. That is weak duality, in one line, with no machinery.
Two things about that table are worth noticing. The first is that a ends at 3 rather than 4: the direct arc costs 4 and the route through b costs 2 + 1 = 3, so the direct arc ends up slack. The second is that one pass over the arcs was enough, because the order they were typed in happened to relax them usefully; the second round is what proves it, by changing nothing.
Take the labels 0, 3, 2, 6 and add 7 to each, giving 7, 10, 9, 13. Every arc constraint still holds — each is a difference, and the seven cancels — and the dual objective is still 13 − 7 = 6. The same tight arcs are still tight.
Now add 5 to one label only. The lab reports the arcs that are violated, in red. This is the contrast that makes the point: the vector floats as a whole and does not float component by component, which is precisely the behaviour of a price.
This is why the lesson is called potentials rather than distances. Calling them distances is not wrong — the normalisation πₛ = 0 makes each label the distance from the source — but it hides the fact that the object is determined only up to a constant, and it makes the next two courses harder than they need to be, where the same potentials are used to reprice a network without changing which route is cheapest.
s>a 4, s>b 2, a>b −3, b>t 2, a>t 6 has a negative cost on it, and the labels settle at 0, 4, 1, 3 with s>a, a>b and b>t tight. The cheapest way to b is through a at 4 − 3 = 1, not the direct arc at 2.
So a negative cost is not a problem in itself — it is perfectly meaningful when an arc earns rather than spends. What cannot be tolerated is a cycle whose total is negative, which is a different thing entirely.
x>y 1, y>z −3, z>x 1, x>z 5. Add the dual constraints round the cycle x, y, z, x: the labels cancel and what is left is 0 ≤ 1 + (−3) + 1 = −1. No vector π can satisfy all three, so the dual is infeasible.
The relaxation finds this by still improving when it should have stopped: the labels go 0, ∞, ∞ then −1, 1, −2 then −2, 0, −3 then −3, −1, −4, one unit lower every round and never settling. The lab names the cycle y, z, x and reports that it costs −1.
The word for this on the primal side is unbounded: send a unit round that cycle as many times as you like and the cost falls without limit. An unbounded primal and an infeasible dual are the pair the duality course described, and here they arrive as a picture you can point at.
One thing deliberately absent from this page is a second algorithm. Dijkstra's algorithm computes the same labels faster on non-negative costs, it belongs to Discrete Mathematics' “Shortest Paths and Dijkstra's Algorithm”, and putting it beside this one would invite the question “which is better” when the question here is “what are these numbers”. They are a dual solution. That is the lesson.
Interactive
The labels are dual variables — prices on the nodes — and a negative cycle is dual infeasibility
Method
Checking is much cheaper than finding, and this is the lesson where that gap is widest.
Zero is a normalisation. Any other value for the source works and shifts every label by the same amount, which the lab will show you; zero is chosen because it makes the labels read as distances.
Relaxing arc (i, j) means: if πᵢ + cᵢⱼ is less than πⱼ, lower πⱼ to it. A round that changes nothing is the stopping condition and the proof of feasibility at once.
There is a negative cycle, the dual is infeasible and the primal unbounded. Report the cycle and what it costs; no set of labels exists to report instead.
πⱼ − πᵢ ≤ cᵢⱼ on every arc, not just the ones on the route you expect. This is one subtraction per arc and it is the whole verification — a feasible π is a certificate that no path is shorter than πₜ − πₛ.
The arcs where the inequality is an equality carry the shortest paths. If more than one tight route reaches the sink, there is more than one shortest path, and that is information rather than ambiguity.
Each block is the labels the relaxation settles on, the arc-by-arc check, and the dual objective. All three are what the lab reports.
Network 1 settles after a single pass because the arcs happen to have been typed in a helpful order; the second round is not wasted, it is the proof. Reorder the arcs in the box and watch the number of rounds change while the answer does not.
For a rehearsal, take network 1 and hand-write the labels 0, 4, 2, 7. Every arc constraint holds, so this is a feasible dual point too — and its objective is 7, which is more than 6 and therefore impossible. Find your error: b>a gives 4 − 2 = 2 > 1, so the point is not feasible after all. This is the whole skill: a claimed certificate is checked arc by arc, not by eye.
The harder rehearsal: on network 3, change y>z from −3 to −2. The cycle now costs zero, the labels settle, and a feasible potential exists. A zero-cost cycle is the boundary case, and it is worth seeing both sides of it.
You should be able to write the shortest-path dual, run the relaxation to a settled vector, check every arc, identify the tight arcs and read the route off them, explain why a constant shift changes nothing, and recognise a negative cycle as dual infeasibility rather than as a failure of the method.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.