Relax every arc, V - 1 times over. After round i every label that has a shortest path of at most i arcs is correct, so V - 1 rounds suffice — a shortest path cannot repeat a vertex. If a round V still improves something then no shortest path exists, and the predecessor pointers hold the negative cycle that is the reason. Nothing here settles a vertex, which is exactly why it survives a negative arc.
Core ideas
The hard idea is the round invariant, because it is about the number of arcs on a path rather than about distance. The stopping rule and the certificate follow.
After one full sweep, every vertex whose shortest path uses one arc is correct; after two, every vertex whose shortest path uses at most two; and so on. A shortest path never repeats a vertex, because removing a repeated stretch cannot make it longer unless that stretch was negative — and if it was, no shortest path exists at all. So V - 1 arcs is the most any shortest path has, and V - 1 rounds is enough.
Dijkstra’s schedule declares a vertex finished and stops relaxing its outgoing arcs. Here every arc is relaxed in every round, so a label that improves late still propagates. On the lab's opening graph the label at vertex 5 improves in the second round, from 2 to -2, and the nearest-first schedule on the same graph returns 2 — the right shape of answer and the wrong number.
If a full round after the V - 1 still changes a label, some path uses V arcs and is therefore shorter than one that repeats no vertex, which means a cycle of negative total weight. Walking the predecessor pointers back V times from a vertex that moved lands inside that cycle, and following them round closes it. On 1>2 1, 2>3 -3, 3>4 1, 4>2 1 the lab returns the cycle 2, 3, 4, 2, which weighs -3 + 1 + 1 = -1.
The material
Why a round is the right unit, why V minus 1 of them suffice, what the arc order changes, and the negative cycle as evidence.
After i complete rounds, for every vertex v whose shortest path from the source uses at most i arcs, d[v] equals that shortest distance.
By induction on i. For i = 0 the only such vertex is the source, whose label is 0.
Assume it after i rounds and let v have a shortest path s, ..., u, v with i + 1 arcs. The prefix to u is itself a shortest path with i arcs, so d[u] is correct after round i, by hypothesis. Round i + 1 relaxes the arc from u to v at some point, and by then d[u] is at most its correct value, so afterwards d[v] is at most d[u] + w, the true shortest distance. The upper-bound invariant of the relaxation step says it is not less, so it is equal.
□
Note what the proof does not need: the arcs may be relaxed in any order within a round, and d[u] may have been improved earlier in the same round, which only helps. That is why the algorithm is indifferent to how the arcs are stored, and also why the number of rounds it actually needs is not.
The lab opens on 1>2 6, 1>3 7, 2>3 8, 2>4 5, 2>5 -4, 3>4 -3, 3>5 9, 4>2 -2, 5>1 2, 5>4 7 from vertex 1. The distances come out 0, 2, 7, 4, -2. The first round reaches 0, 2, 7, 4, 2 and the second improves only vertex 5, to -2; the third changes nothing and the run stops after 3 rounds and 30 relaxations. Floyd's all-pairs matrix, computed separately, gives the same row from vertex 1. The nearest-first schedule gives 0, 2, 7, 4, 2.
The route to vertex 2 is 1, 3, 4, 2, three arcs, at 7 - 3 - 2 = 2. Its label was already final after the first round even though its path has three arcs, because the arcs happened to be swept in an order that carried the improvement all the way along in one pass. The invariant promises correctness by round three; it does not forbid getting there sooner.
Take a chain of five arcs each of weight 1, and type it backwards: 5>6 1, 4>5 1, 3>4 1, 2>3 1, 1>2 1. Each round pushes the frontier forward by exactly one arc, so the run takes 6 rounds and 20 relaxations, and the round each label became final is 0, 1, 2, 3, 4, 5. Type the same five arcs forwards and one sweep carries the improvement the whole way: 2 rounds, 10 relaxations, and every label final in round 1. Both give the distances 0, 1, 2, 3, 4, 5.
That is the cleanest example on this course of a count moving while an answer does not. Same vertices, same arcs, same weights, same distances; two thirds less work. And it is also why the bound is V - 1 rounds rather than something smaller: the backwards chain needs every one of them, so no smaller number is correct for all inputs.
If a round after the V - 1 improves any label, then some cycle reachable from the source has negative total weight, and no shortest path exists to the vertices beyond it. If no such round improves anything, every label is a true shortest distance.
The forward direction is the round invariant read backwards: if no negative cycle is reachable then every shortest path has at most V - 1 arcs, so round V - 1 finished the job and round V finds nothing. If something does improve, the improving path uses V arcs, hence repeats a vertex, hence contains a cycle; and it could only be an improvement if that cycle is negative.
On 1>2 1, 2>3 -3, 3>4 1, 4>2 1 the lab runs all four rounds, something changes in the last, and 16 relaxations are performed. The labels it prints, 0, -3, -5, -4, are not distances and the panel does not present them as any: they are one lap further round the loop than the previous values. What it returns instead is the cycle 2, 3, 4, 2, whose weight is -1, so every lap subtracts one more.
A flag saying “negative cycle” would leave the reader with nowhere to go. The cycle itself is actionable: in a scheduling or currency model it names the loop that must be broken, and in a debugging session it names the arc whose weight was typed with the wrong sign.
Measured against proved. On the opening graph: 3 rounds, 30 relaxations, five distances. On the backwards chain: 6 rounds, 20 relaxations. The bound is O(V E), from V - 1 rounds of E relaxations each, and it is attained — the backwards chain needs every round. What the measurements cannot tell you is that no ordering forces more than V - 1, and that is what the invariant is for.
Interactive
One round per arc on a shortest path, and a round that still improves something is a negative cycle
Method
One sweep is one unit of progress. Count the sweeps, not the improvements.
Skipping arcs whose tails did not change is a real optimisation and it changes what the round invariant says. Get the plain version right first: the correctness argument is about complete sweeps, and a partial sweep needs its own argument.
If a full sweep improves no label, no later sweep can either, since nothing has changed for it to build on. On the forwards chain this cuts six rounds to two. It is the one shortcut that costs nothing to justify.
The V-th round is not part of computing the distances; it is the test for whether they mean anything. Code that stops at V - 1 returns numbers on a graph with a negative cycle and gives no sign that they are not distances.
From a vertex that improved in the last round, follow the predecessor pointers back V times to land inside the cycle, then follow them until you return to where you started. That is the evidence, and it is what makes the result actionable rather than merely negative.
The arcs are 1>2 6, 1>3 7, 2>3 8, 2>4 5, 2>5 -4, 3>4 -3, 3>5 9, 4>2 -2, 5>1 2, 5>4 7, swept in that order, from vertex 1.
The round-final column is at most the arc-count column at every vertex, and strictly below it at three of them. That is the invariant doing exactly what it promises and no more: round i guarantees correctness for paths of at most i arcs, and a lucky sweep order can deliver a four-arc path in round two.
Vertex 5 is where the nearest-first schedule breaks. That schedule settles 5 at 2 when 2 is the smallest unfinished label, and never revisits it; the arc 2>5 of weight -4 then improves d[2]'s own route too late to help. Here every arc is relaxed in every round, so nothing is too late.
For a faded rehearsal, change 5>1 2 to 5>1 -2 and predict what the lab reports before running it. The supplied first move is this: the route to 5 costs -2, so going on to 1 now costs -4, and 1 already had a label of 0. Say whether that makes the loop through 1, 3, 4, 2, 5 negative, what the extra round will find, and what the panel should print instead of distances.
You should be able to sweep the arcs in order recording the label table per round, state what round i guarantees, explain why V - 1 is both sufficient and tight, run the extra round as a test rather than as part of the computation, and walk the predecessor pointers back to a negative cycle.
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.