Every shortest-path algorithm on this course is the same step applied on a different schedule: if going to u and then along an edge beats the best known route to v, write the better number down. The step never makes a label too small, so a schedule can only be judged on whether it finishes and on what it costs. Three schedules are run side by side on the graph you type, and all three agree with an independent answer.
Core ideas
The hard idea is that the schedule is a separate question from the step. The invariant is what makes that separation legitimate.
Every label d[v] starts at infinity and only ever falls, and it always records the length of some actual route from the source — which is why it can never drop below the true distance. The lab checks that invariant after every single step, against distances computed by a different algorithm entirely, and reports both that it held and that every label ended exact.
On the lab's opening graph the three schedules all reach the distances 0, 7, 9, 20, 20, 11 from vertex 1. What differs is the cost: taking the nearest unfinished vertex from a heap does 18 relaxations with 8 pushes and 8 pops; finding the same vertex by scanning every label does 18 relaxations and 42 label reads; relaxing the edges in the order they were typed, round after round, does 36. Same six numbers, twice the work at one end.
The heap schedule declares a vertex finished the moment it is the closest unfinished one, and never looks at it again. That is sound only because no edge can reduce a distance — with every weight at least 0, nothing reached later can offer a cheaper route back. Where that fails, the schedule fails, and on this undirected graph it fails for a reason worth being precise about: an edge of negative weight that can be walked in both directions IS a negative cycle.
The material
The relaxation step, the invariant it maintains, the three schedules with their counts, and what the reference column is not.
Given labels d and an edge from u to v of weight w, to relax that edge is to test whether d[u] + w is less than d[v], and if so to set d[v] = d[u] + w and record u as v's predecessor. The label d[v] is initialised to infinity for every vertex but the source, whose label is 0.
At every moment during any sequence of relaxations, d[v] is either infinite or the length of some path from the source to v. In particular d[v] is never less than the true shortest distance to v.
By induction on the number of relaxations performed. Before any, only the source has a finite label and 0 is the length of the empty path.
Suppose the claim holds and the edge from u to v is relaxed, setting d[v] = d[u] + w. By hypothesis d[u] is the length of some path from the source to u; appending the edge gives a path to v of length exactly d[u] + w. So the new label is again the length of a path, and no path is shorter than the shortest one.
□
That theorem is why a schedule cannot be wrong in the direction of underestimating, and it is what makes the three schedules comparable. Each is a rule for which edge to relax next; none of them can produce a number below the truth; the only questions left are whether the labels ever reach the truth, and how much work that takes.
The lab opens on 1-2 7, 1-3 9, 1-6 14, 2-3 10, 2-4 15, 3-4 11, 3-6 2, 4-5 6, 5-6 9 from vertex 1. All three schedules reach 0, 7, 9, 20, 20, 11, and so does an independently written Dijkstra from another Subject that knows nothing about this representation. The route to vertex 5 is 1, 3, 6, 5, at 9 + 2 + 9 = 20. The counts: heap 18 relaxations, 8 pushes, 8 pops, 15 key comparisons; scan 18 relaxations and 42 label reads; arc order 36 relaxations.
Two numbers in there are worth dwelling on. The heap and the scan perform the same 18 relaxations, because they make the same choices — they differ only in how the choice is found, which is 15 heap comparisons against 42 label reads. And the arc-order schedule does exactly twice as many relaxations, because it needs a second sweep to confirm that the first one settled everything.
The lab's other presets move those numbers in opposite directions. On a chain of six edges the scan does 56 label reads where the heap does 7 pushes, 7 pops and no key comparisons at all; on ten edges over five vertices the scan does 30 reads against the heap's 14 comparisons, 7 pushes and 7 pops. The heap's advantage is largest where the frontier is small, which is the sparse case, and that is the shape of the usual advice.
The panel prints E times the integer part of log₂ V, labelled for reference: 18 on the opening graph, since it has nine edges and six vertices. The measured relaxation count is also 18 and that is a coincidence of this graph; on the chain the reference is 12 and the heap does 12 relaxations with quite different heap traffic. No verdict is read off the column, and none should be: it is a scale to watch the counts against as the graph changes.
The edges here are undirected, and that is deliberate, because it is what lets the answers be checked live against an undirected implementation written for another Subject. It has a consequence the panel states outright: on an undirected graph a negative weight is a negative cycle. Walk such an edge and walk back, and the total has fallen by twice the weight; do it again and it falls further. No shortest path exists to anything on that side of the graph.
The lab will let you type one so that you can see what happens, and what happens is not an error message. On 1-2 -3, 2-3 4 the heap schedule returns labels of -6, -3 and 1 — including a label of -6 for the source itself, whose distance to itself is 0. The rounds method on the same graph returns the cycle 1, 2, 1 as a certificate. Negative weights belong to directed arcs, and they are the subject of “Negative Weights and Bellman–Ford”.
Measured beside proved, one last time. The three schedules agreeing on six numbers, on four presets, is evidence that the step is indifferent to order. The theorem is that on any graph with no negative weight, the nearest-first schedule settles every vertex exactly once with its true distance, and the proof is a separate argument about the smallest unfinished label — not something the agreement could establish, because agreement on four graphs is agreement on four graphs.
Interactive
Three orders for the same step; the labels never drop below the true distance and the page checks it
Method
The step is fixed. Everything you decide is about order.
Every algorithm in this module performs exactly d[v] = min(d[v], d[u] + w) and records a predecessor. Bugs at this level are rare; bugs in the schedule are common, and keeping the step separate in your head is what makes the difference visible.
After any prefix of the relaxations, every finite label should be the length of a real path. That is checkable at every step, whereas the final answer is checkable only at the end. The lab reports both, and it is the per-step check that localises a mistake.
A small frontier favours the heap; a dense graph where almost every vertex is a candidate at once narrows the gap, because the scan's V reads are then cheap relative to the heap traffic. The lab prints both counters on whatever you type, which is a better guide than a rule of thumb.
Nearest-first is correct because no later edge can reduce a settled label, and that argument uses non-negativity and nothing else. On these undirected edges a negative weight is not merely awkward, it is a negative cycle, and the question stops having an answer rather than becoming harder.
The graph is 1-2 7, 1-3 9, 1-6 14, 2-3 10, 2-4 15, 3-4 11, 3-6 2, 4-5 6, 5-6 9, undirected, and the source is vertex 1.
Watch vertex 4. Its label was 22 after vertex 2 was settled and fell to 20 when vertex 3 was settled — an improvement to an unsettled vertex, which is ordinary. What never happens on this graph is an improvement to a SETTLED vertex, and that is the property nearest-first depends on. It is guaranteed by the weights being non-negative and by nothing else.
Notice that the heap and the scan performed the same 18 relaxations. They make identical choices; the 15 comparisons and the 42 reads are two ways of finding the same minimum. The arc-order schedule, which never asks which vertex is closest, pays 36 relaxations for a saving of all the bookkeeping — and on a graph where the arcs happen to be in a good order it would pay far less, which is what “Negative Weights and Bellman–Ford” is about.
For a faded rehearsal, delete the edge 3-6 and predict all six distances before running it. The supplied first move is this: the route to 6 through 3 cost 9 + 2 = 11, and without it the only remaining routes to 6 are the direct edge at 14 and the way round through 5. Say what d[6] becomes, then say what happens to d[5], and check both.
You should be able to state the relaxation step and the invariant, run nearest-first by hand recording the settle order, say what the other two schedules do differently, read the three counter sets as costs rather than as answers, and say precisely why a negative weight on an undirected edge ends the question.
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.