05You Can Only See One Thing at a Time

01The graph you cannot see, and the one move you have

Page 4 let you randomise the algorithm to buy an average; this page takes something away instead, and what it takes is sight.

There is a graph in front of you, 8 vertices joined by 9 edges, and every one of those edges points one way. You are standing on one of them, S, and you may ask exactly one kind of question. Who are this vertex's neighbours? Ask it at S and two names come back, because two edges leave S. Ask it at C and one name comes back. That is the entire channel. Nothing you can ask returns a distance, a route, or a count of anything.

You will want to object, and the objection is fair as far as it goes. The graph is drawn right here on the page, in ink, all 9 edges of it. But look at what the drawing actually hands you. It hands you eight discs and nine lines. It does not tell you how far G sits from S, or which of those 9 lines carry a shortest route, or whether a route exists at all. The fog is a fact about the answer, not about the picture. Distances, reachability, which edges belong to the tree: none of those are drawn anywhere, and none of them exist until you build them one probe at a time.

The arithmetic of that constraint is worth doing once, now, while it is still cheap. Each of the 8 vertices can be probed once, so 8 probes exhaust the graph. Each probe reads one neighbour list, and because these edges point one way, each of the 9 edges puts an entry in exactly one list. So exhausting the graph reads 9 entries in total, one per edge. That is the whole budget, and no cleverness shrinks it. What is left to choose is the order you spend it in.

So the instrument for the rest of this page opens fogged, and it means it. Eight grey discs, no edges drawn between them at all, and one held line of text: nothing is known yet. A single button, PROBE THIS VERTEX, un-fogs one vertex's neighbours and nothing else. The policy dropdown stays locked until the fourth press, so you spend four probes genuinely not knowing where you are, and the constraint becomes a memory rather than a claim. Then seven orders unlock over that same fogged graph, and the same record array fills differently under every one of them. Nine algorithms you have already heard of are waiting inside this page. Not one of them is named on the dial.

What can you do with what a probe returns? Exactly one thing, which is why this page has one verb rather than nine. You have reached somewhere and stored a fact about it. The probe hands you an edge leading out of that somewhere. So look along the edge, ask whether the far end's stored fact gets better by coming through you, and if it does, improve it. That is relaxation, and it is the only move on this page. Every policy you are about to meet is built from it.

A universal claim is worth two sentences of honesty, so here they are. One policy late on this page improves a fact by composing two facts it already holds, with no new edge involved. Another never stands anywhere on the graph, so it has no far end to look toward. Both are named as departures when they arrive, instead of quietly falsifying a slogan you were asked to carry. Everything else, all seven orders and the famous names behind them, is one move spent in a different sequence. Look along one edge, ask whether a stored fact gets better, and that is the entire move — with two labelled exits we will name when we reach them.

02Two fields, three buckets, one free variable

The move needs somewhere to put what it learns, and a vertex remembers exactly two things. The first is who found me, a single source: one arrow, pointing back at the vertex we were standing on when this one turned up. The second is how good the claim is, a single score. Nothing else fits in there. No list of routes, no history, no runner-up. Say a probe from u looks along an edge of weight 5, and u is already holding a score of 4. Then v takes the score 9, and v's arrow gets pointed at u. That is one vertex's entire memory, filled.

Follow the arrows backwards from any vertex and a route falls out, one hop at a time, until you land on the start. Collect every arrow on the graph and you have a tree, because each vertex carries one parent and there is nowhere for a second route to hide. Now the careful sentence, since the obvious version decays under use. Walking the arrows back gives you the route by which this policy found you, and nothing stronger than that. It is not automatically the shortest, or the cheapest, or the one with the fewest hops. What that route is worth is exactly what the policy's reason buys, and that is this whole page compressed into a line.

With a record in place, every vertex on the fogged graph sits in one of three states. Unseen means we have never heard the name. Guessed means some probe has written a source and a score into it, and both can still change. Settled means we have stopped doubting it. A probe moves a vertex from unseen to guessed, which needs no justification at all, since hearing a name is not a claim about anything. Moving a vertex from guessed to settled is a different act entirely, and it is the only decision any policy on this page ever makes.

One property of the guessed bucket is free right now and load-bearing three times later, so take it while it is cheap. A guessed score is not a guess about the world. It is the cost of a route we have genuinely walked, through settled vertices only, ending here. So v's 9 is not an estimate of v's true distance. It is a real 9, a trip somebody could take today. The truth about v may be smaller than 9 and can never be larger. Which means a score only ever falls: our one move improves a stored fact or leaves it alone, and it never inflates one.

Say the awkward part now, rather than let it surface later as a malfunction. Not every policy ahead uses all three buckets. One of them never fills settled at all, and that turns out to be the most interesting thing about it. One has no unseen bucket, because every edge is visible from the first instant. One walks away from the picture completely. Each will say so as it arrives, and none of them is the frame breaking.

So take stock of what is now nailed down. The move is fixed: look along one edge, and see whether a stored fact gets better. The shape of the memory is fixed too, at one source and one score for every vertex. Free are the units of the score and the choice of which guessed vertex to settle next. Those two are the same choice seen twice, because the order is nearly always induced by the score, meaning settle the extreme-scoring guessed vertex. A policy is a score, plus the order that score induces.

Page 4's fraction says that in arithmetic. Its numerator is the information the answer needs, its denominator is what one probe hands back one vertex's neighbours, and here neither half can move. So the lever is the order in which you spend the denominator, which is the paragraph above with numbers under it. We will spend most of this page finding out how much that one variable buys, and then we will run out of order, and the last stretch unfreezes what we froze here, one thing at a time. Two things are frozen and one thing is free, so the first question is whether the free one can be spent badly.

03One wrong settle, then the reason it needed

Set the dial to FIFO ring — first in, first out — put a 5 on the edge from S to B, and press. B sits one hop from the source, so it comes out of the queue almost immediately and turns settled, with the cost readout under it reading 5. You can already see the cheaper way from where you are sitting: S to A to C to B, three edges of 1 each, 3 in total. The machine has found A too. It simply stopped asking about B. Four words print under the frozen frame: you claimed too early. Nothing else appears, nothing is named, and no repair is offered.

Sit with that for a moment, because it is stranger than a bug. The order did not misread anything: the FIFO ring was asked which guessed vertex to finish next, it answered v, and v was the one that had been waiting longest. Every part of the machine did exactly the job it was given. What went wrong sits upstream of all of it: something moved v into the settled bucket, and moving it there froze a cost readout you can see is beatable. Nothing in the run had been asked to check that number.

So the question you are holding is a fair one. Why was that allowed? To settle a vertex is to make a claim: this score can no longer come down. The claim is about the whole rest of the graph, most of which is still fogged, so something has to stand behind it. Nothing in the three buckets stands behind it, and nothing in the two-field record does either. The only thing left in the room is the order in which you settle, and that is what it has been doing all along. Settling is a claim, and the order is its reason.

The FIFO ring did have a reason, and we will prove it properly in a moment. The reason was simply not true in a world with a 5 in it. That is the shape of everything ahead. The names ahead are all answers to the same question — each legal exactly while its own assumption holds, and wrong the instant it stops. You now have a way of meeting an algorithm you have never seen that does not involve memorising it. From here the page asks one question of everything it meets: what is this order's reason, and what breaks it?

04The queue is two blocks, and that is the whole proof

The FIFO ring's reason starts as a question, and before anything moves you have to commit to an answer: can the queue ever hold something three hops out and something five hops out at the same time? The strip under the graph stays grey and the step button stays dead until you have said yes or no, which is deliberate. A prediction you never made is a prediction you cannot be surprised by. Answer, then press.

Press once. S comes out, A and B go in, and the queue reads [A1 B1] — one block, both of them one hop from the source. Press again. A comes out and C goes in, so the queue is [B1 | C2], a run of ones followed by a run of twos. Press again and B leaves, E arrives, and the twos close ranks into [C2 E2]. Carry on to the end and the eight presses read one, two, one, two, one, one, one, empty. It is never three.

That is not a habit of this particular eight-vertex graph. A vertex scored k+1 can only enter the queue during the pop of a vertex scored k, because draining an old ring is the only occasion on which you discover anything new. Every (k+1) in there was bought by a k coming out. So the largest score in the queue exceeds the smallest by at most one, and a third block has nowhere to come from.

Now close it out loud, because a pattern you watched is not yet a fact you own. A vertex v is first sighted while ring k−1 is draining, so v lands at ring k. Suppose some route reached v in j edges, with j smaller than k. Its second-to-last vertex sits at ring j−1, which is at most ring k−2 (j ≤ k−1), and that ring was drained in full before ring k−1 ever opened. Draining a vertex reads every one of its neighbours. So v would already have been sighted, and it was not. No such route exists, so first sighting is cheapest sighting — on every graph, not just the one in front of you.

One assumption did all of that work, and it deserves its own colour: every edge costs exactly one. That is the whole hypothesis. FIFO order is distance order because arrival order and cost order are the same order when every step is priced the same. Nothing in the argument above mentions a weight, for the plain reason that nothing in the queue ever reads one.

So drag S→B from 1 up to 5, and watch the HOPS row rather than the graph. It does not move. Not a digit, not a block boundary, not one parent arrow. B is still exactly one hop from S, because a hop count counts edges and the queue never asked what an edge cost. The invariant is intact and everything proved four paragraphs ago is still true.

The second row is where it happens, and it happens at F. BFS found F down the short chain S→B→E→F, which now costs 7. The cheapest route in is the longer one, S→A→C→D→F (1 + 1 + 1 + 1 = 4). So F's stored cost is wrong by 3 while its hop count of 3 is still exactly right, and F's parent arrow points at E when the cheapest way in has become D (D costs 3, and 3 + 1 = 4). G inherits it downstream: the chain gives 7 + 1 = 8 where the truth is 4 + 1 = 5. The queue kept its promise. The promise stopped being about cost.

You are already reaching for the repair, and you are right. Split that 5 into five unit edges and BFS answers correctly again, at a price of 4 new vertices and 4 new edges. Now set the weight to 1,000,000. The identical repair asks you for 999,999 vertices, and the absurdity prices it faster than any argument could. So the priority queue arriving shortly is not new machinery — it is your own subdivision idea, stored efficiently.

05Settle the newest instead, and watch what it settles

Change one thing on the dial, from FIFO ring to LIFO dive: settle the guessed vertex discovered most recently, not the one discovered first. Predict the record before you press, because the arrows from the last run are still on screen and you get to watch them be overwritten. What comes out is a dive: one long thread pushed as deep as the graph allows, then a slow walk back up it. Nothing about that thread is short. Follow its arrows backwards and you get the route this policy happened to take, which is the weak and true version of what the record ever promised. So the useful question is not whether the answer came out wrong. This order settles nothing about distance, so what does it settle?

One correction first, because the usual shortcut is a bug. Swapping the queue for a stack does not give you this dive. That version pushes all of a vertex's neighbours at once, pushes some vertices more than once, and finishes them in an order that is not this one. The stack here holds vertices with unfinished business, which is a different thing entirely. Each entry is a frame: the vertex, plus a cursor sitting partway along its neighbour list. A vertex stays open for as long as its cursor still has somewhere to go, and that is what makes the dive real rather than a container swap.

Two readings get stamped on each vertex, and they are called opened_at and closed_at. Never d. Everywhere else on this page d means distance, and letting one letter do both jobs quietly teaches that a clock reading and a distance are the same kind of number. They are not. Every vertex opens once and closes once, so on an eight-vertex graph the clock stops at 2 × 8 = 16. Sixteen ticks, and sixteen symbols on the tape.

Fig. 3 draws the open set as a literal vertical stack, one frame per open vertex, cursor and all, with a bracket tape scrolling underneath it. Run it on the eight-vertex dag. S opens at tick 1 and does not close until tick 16, so it holds everything. A opens at 2 and closes at 11, and B does not open until 12. Hover any two vertices and their two intervals light up. They nest, or they miss entirely. They never half-overlap, and the caption under every pop says why in six words: only the frame on top can close. Anything opened later was pushed above, so it has to close earlier — which is the entire reason that tape balances.

That geometry buys something at once. Suppose you are exploring an edge and the far end is still open. Its interval has to contain yours, so it is your own ancestor. An edge into a still-open frame is an edge pointing back up your own call stack. Toggle the extra edge G→C on and watch it happen. G opens at tick 6 and C has been open since tick 3, so G→C lands inside a live frame, and the cycle it closes is C→D→F→G→C, four edges long. In a dag that toggle is off and no such edge exists anywhere.

So the clocks hand you a schedule for free. Reverse the finish order: S closed at 16, then B at 15, E at 14, A at 11, C at 10, D at 9, F at 8, and G at 7. That gives the order S, B, E, A, C, D, F, G. All nine edges point forwards along that list — S→A, S→B, A→C, B→C, B→E, C→D, D→F, E→F, F→G. The reason is three lines rather than nine checks. Exploring the edge from u to v, the far end v is either unseen, in which case v closes before u, or already closed. It cannot be still open, because still open is a back edge and a dag has none. Either way v closes first, so closed last must go first.

There is one thing we are not going to do here. A famous two-pass trick reuses this finish order to find the clusters that can all reach each other, and its correctness turns on a claim about which cluster finishes last. A clause that merely looks like a proof is worse than an omission, so you get the question instead. The question earns its keep on its own: a cycle is a set of places that can all reach each other, which is can I drive there and get back? That is the same shape as the toggle you just flipped. A back edge is the circular-dependency error your build system prints, and now you can say why it is called that.

06Nearest first, and the one clause it spends

The LIFO dive settled closure, and the FIFO ring settled distance only while every edge cost one. So ask the obvious next question with the obvious candidate. Set the dial to nearest-first: score the vertices by accumulated weight and settle the smallest. Before asking whether that is legal, make its one question expensive. Settle a vertex on an eight-vertex graph, then find the next-nearest by eye. You scan seven candidates. Do it again and you scan six, then five, then four. Play the run out and the scans come to 28 7+6+5+4+3+2+1 on that one eight-vertex graph. Nothing else about the move changed, so that scan is the entire new bill.

Who is nearest? is a question somebody now has to keep answering, and a heap is the object that answers it. That is all it does, and it hands back the nearest for nothing, because the nearest is sitting at the top. What costs is the repair afterwards, and on eight vertices that re-sinks one entry through 3 levels lg 8 = 3 instead of rescanning all 7. The scan grows with the graph and the sink stays a handful of levels, so the gap widens. It is also the subdivision you invented, stored efficiently: where that 1,000,000-weight edge asked you for 999,999 waypoints, the heap holds one entry carrying the number instead.

Now the reason, stated forwards, in one sentence. Any other route to the nearest unsettled vertex has to leave the settled set through some vertex already at least as far out, and the rest can only add weight. The first half is airtight already, because a guessed score is the cost of a route you have genuinely found through settled vertices. So it is never a guess about the world, and it can only ever come down. Which leaves the coloured clause carrying the whole claim by itself. Most treatments smear that assumption across four steps of a contradiction proof, and an assumption you cannot point at is one you cannot violate on purpose.

So violate it, with your own hand on the weight slider. Three edges are enough: s to a costs 2, s to b costs 5, and b to a costs -4. Nearest-first compares 2 against 5, settles a at 2, and stops doubting it. The genuine best route into a costs 1 5 - 4, and it runs through the vertex that looked further away. The moment the slider crosses zero the coloured clause greys out on the instrument, and a readout names the settle that just became illegal. Drag that edge back above zero and the same settle is sound again. You built the counterexample, and we only quoted the sentence that died.

Two things here wear nearly the same word, so separate them now. One negative edge is fine. There is still a best answer, and nearest-first simply cannot reach it — the route costing 1 exists whether or not this policy ever finds it. A negative loop is not a hard problem but an ill-posed one. Set a to b at 1 and b to a at -4, and one lap round saves 3. Eleven laps save 33, a hundred laps save 300, and there is no shortest path left to find. The first is a policy failing, and the second is the question failing.

What you hold now is not the prohibition no negatives, which is a rule you can recite and nothing more. You hold the exact inequality this policy spends, the reason it was cheap, and a three-edge graph that kills it. Every remaining setting on the dial gets judged the same way. Your inequality just died — so what is the cheapest possible replacement reason?

07No reason at all, the licence, and the order you get free

Stop giving reasons: relax every edge, then relax every edge again, and keep going until nothing changes. That is the policy you just proposed, and it is a real one with a famous name. Set the dial to all-edges-repeatedly, then carry the negative edge back onto the eight-vertex graph: drag B→C down to −4, the way you just did on the three-edge one. The answers come out right. So the interesting question is no longer whether this works, but how many times you have to do it.

To find that number, stop watching edges and watch one whole pass. A pass has some order, but the order does not matter, because a pass relaxes every edge before it ends. Now hold the true shortest route to any one vertex in your head as what it is: a specific sequence of edges, run end to end. Somewhere inside every pass sits the next unfinished edge of that sequence, and relaxing it makes the far end correct. So each pass pushes every shortest path forward by at least one edge, wherever those edges happened to fall in the order. Nothing is being claimed about which vertices are finished. Only that each true route advances by one.

Which turns the count into a question about length. How many edges can a shortest path have? Walk it. A positive loop only wastes weight, so no cheapest route carries one. A zero loop can be cut out with nothing lost either way. A negative loop means no finite answer exists at all, so there is nothing to bound. What survives is the line that does the work: a shortest path never visits a vertex twice. Eight vertices, therefore at most seven edges, therefore seven passes — and the badge on the pass counter now says something you derived rather than something we printed.

The eighth pass comes free, and it is the best part. Run it. If a graph is honest, pass 8 changes nothing, because seven passes already finished every path. If pass 8 does still improve some vertex, that vertex is reachable from a negative cycle. It may be standing on one, or it may merely sit downstream of one and inherit the leak, and either way no finite answer exists for it. The loop bound and the impossibility detector are the same number. One counter tells you when to stop and whether stopping meant anything.

Two things on the instrument look broken here and are not. The settled bucket never fills. This policy certifies nothing per step, which is precisely why it needs seven passes instead of one clever argument, so the blank panel is the lesson rather than a rendering fault. And the scan counter runs up a bill: seven passes across nine edges is (7 × 9 = 63) sixty-three relaxations, the first time on this page that any policy has paid to walk the whole edge list. It bought certainty with an invoice instead of an inequality.

Full passes obviously work. So ask the sharper version: how much of that survives if you stop doing full passes? Flip the junk toggle. It shovels deliberately useless relaxations in between the useful ones — the same edge twice, a dead edge, an edge whose far end is already better off. Try to make the answer wrong. You cannot. Relax the edges of a shortest path in order and its endpoint ends up correct regardless of how much unrelated work is stirred in between.

That word is doing more than it looks. It is safe for a reason you already hold: a score is always the cost of a route you actually found, so any extra relaxation can only push it toward the truth and never away from it. And it is what makes order the only variable on this page, because without it every argument here would be private to its own algorithm. Read it forwards and a policy's entire job collapses to one line. Eventually touch each path's edges in order. That is the whole specification, and nothing in it mentions a heap, a queue, or a reason.

So ask when "in order" comes for nothing. It does when the graph already carries an order — and you built one two policies ago, out of finish times, by reading them backwards. So set the dial to topological sweep. A directed acyclic graph has no back edges, so its topological order relaxes every path's edges in order by construction. One sweep. Eight vertices, nine edges, no repeats, and negative weights are suddenly fine, because nothing here ever needed them positive — that was nearest-first's private hypothesis, not a fact about graphs. Watch the heap panel empty, because the topology now answers for free the only question the heap ever answered. Which is worth one question of your own before you read on, since it is the half of this that travels furthest. The topology handed you a safe order for nothing. Name one other thing that could.

08The hinge, and retuning the world until the fast policy is legal

We have run out of order. Everything from here unfreezes something we froze at the start, one thing at a time, and every unfreezing has a famous name attached to it. We fixed the move, we fixed the shape of the memory, and we left ourselves a single free variable. Four things come loose over the rest of this page: the graph, the index, what you settle, and the edges themselves. This one takes the graph.

Go back to the settle that went wrong the moment an edge went negative, because the diagnosis matters far more than the repair. Nearest-first spends exactly one inequality, and we set it in its own colour: the rest can only add weight. A negative edge does not make that sentence a poor fit for this particular order. It makes it false about this world. The order was never the broken part. So there are exactly two moves available, and both of them are honest. Find an order that never leans on the inequality, which is all-edges-repeatedly at |V|−1 passes, so 7 passes for an 8-vertex graph. Or leave the order alone and make the inequality true.

The cheap second repair is the one everybody reaches for. Lift every edge by a constant until nothing is negative any more. Take two routes from s to t. One crosses five edges for a total of 9, the other crosses two edges for a total of 12, so the five-edge route wins. Now add 5 to every edge in the graph. The long route gains 25 and lands on 34, the short one gains 10 and lands on 22, and the winner has flipped. A flat per-edge surcharge charges you once per hop, so it taxes length. That is not a wrong amount. It is the wrong shape, and it quietly replaces the question you were asking.

The charge has to land on vertices instead. Give every vertex v an altitude h(v), and reweight each edge from w(u,v) to w(u,v) + h(u) − h(v). Walk any route from s to t and add the new labels up. Every vertex in the middle shows up twice, once as the +h(u) of the edge leaving it and once as the −h(v) of the edge arriving, so it cancels. A route whose real total is W now reads W + h(s) − h(t), and nothing in that correction mentions the route. Two routes between the same pair of ends shift by the identical amount, so their ranking cannot move. Put the same two routes through it and watch. Give s an altitude of 0 and t an altitude of 4. The five-edge route reads 9 + 0 − 4 = 5 and the two-edge route reads 12 + 0 − 4 = 8, so the gap is still 3 and the five-edge route still wins. Every altitude in the middle cancelled, every edge label on the screen changed, and the winning route did not move a pixel. This is page 2's potential function aimed at edges rather than operations, carrying one new demand: it has to preserve an ordering, not merely a total.

So which altitudes? We need w(u,v) + h(u) − h(v) ≥ 0 on every edge, which rearranges to h(v) ≤ h(u) + w(u,v). That is the triangle inequality, and shortest distances satisfy it by construction. So use shortest distances as the altitudes. Picture a phantom vertex joined to all 8 of ours at cost zero, and take its distances. Equivalently — and this is what the instrument actually runs — start every altitude at 0 and sweep the real edge list with all-edges-repeatedly. Our graph carries 8 vertices and 9 edges, so that slow run is 7 passes across 9 edges, which is 63 relaxations.

Now price what those 63 bought, because the price is the part worth arguing about. For a single source the retuning buys you nothing at all. You ran the slow policy in order to avoid running the slow policy, and you are standing where you started. For every source it is the whole game, because the 8 altitudes do not depend on which vertex you start from. One set of altitudes legalises nearest-first for all 8 sources at once. Price both sides. Eight slow runs would be 8 × 63 = 504 relaxations. One slow run of 63, followed by eight nearest-first runs that touch each of the 9 edges once, is 63 + 72 = 135. You pay the slow price once and spend it eight times — which is page 1's shape wearing new clothes.

09Order by permission, not by vertex

Every policy so far has ordered vertices, and nothing ever said you had to. The altitudes left us wanting every source at once, and that is a different shape of question. You have already met the alternative without noticing it. The pass counter that ran seven passes for an eight-vertex graph was a permission parameter all along. After pass k, the final answers are exactly the routes allowed at most k edges. Change what the permission is about, from a count of edges to a set of usable waypoints, and all-pairs collapses into three plain loops.

Park the eight-vertex graph and take a four-vertex one, so that the whole answer fits on screen at once: 16 pairs, laid out as a table. Take the slider labelled waypoints you are allowed to use and leave it at k = 0 for a moment. Nothing is admitted yet, so every cell of that four-by-four table is either a single edge or INF. That is the parameter's entire meaning, set down before anything moves. Now walk the slider up and watch one number, the best route from vertex 1 to vertex 4. It starts as the direct edge 1→4 = 9. The readout then prints 9, then 9, then 8, then 6. Admitting vertex 1 changes nothing, since vertex 1 is an endpoint rather than a waypoint. Admitting vertex 2 opens 1→2→4 = 3 + 5 = 8. Admitting vertex 3 opens 1→2→3→4 = 3 + 2 + 1 = 6.

Look hard at that last reroute, because it is the part every course skips. At k = 3 the table never walks the three-edge path and never adds up its three weights. It reads two cells that already existed and adds them. The best route from 1 to 3 is 5, and the best route from 3 to 4 is 1. Both were already in the table under the previous guest list {1, 2}, where 1→2→3 = 5 had beaten the direct edge of 8. So the new answer of 6 is two lookups and one addition. Neither half needed vertex 3 at all.

That is not a coincidence of this graph, and the reason is one line you already own. If the best route under guest list k genuinely uses k, it uses k exactly once, because going round twice can only add weight. So the route splits at k into two pieces, and each piece avoids k by construction. Both pieces are therefore answers the previous guest list already computed, which is why both halves of the split are lookups rather than searches. And it is why k has to be the outer loop. k is not a step and not an iteration index. It says which answers exist yet.

Two things break here, and both are events worth naming rather than contradictions to be found. You asked for an answer per pair, so the memory became a table, 16 cells for four vertices. This is also the first policy whose move composes two stored facts instead of a fact and an edge. No edge from 1 to 3 was looked along, and nobody reached anything. It refuses the fog outright, because it wants the whole map before it begins. What that purchase buys is 4 × 4 × 4 = 64 cell updates, three loops, and no data structure at all. Every pair is answered at once.

The last thing this policy hands you is cheaper than it looks, and it needs no widget to believe. Hold the three loops exactly as they stand and change only the two operators in the inner line. Swap (min, +) for (OR, AND) and the same 64 updates answer reachability instead of distance. Swap in (max, min) and each cell reports the widest bottleneck on the best route between its two ends. Swap in (max, ×) with edge weights read as probabilities and each cell reports the most reliable route. One loop, four algorithms, and the only thing that changed was which two operators sit in one line.

10Settle an edge, then settle nothing at all

Two of the hinge's four are spent, and the third was what you settle. Nearest-first scores a vertex by u.d + w(u,v); change that to w(u,v) alone, and then say what the one character did. The term you deleted was the weight of the whole route behind u. What is left is the price of a single edge, judged on its own. So the score has stopped measuring anything about the source. And the free variable was never only the order, because a score you change is a guarantee you change.

Run both scores on one small graph and read the two answers side by side. Five vertices, S, A, B, C, T, and six edges: S-A 2, A-B 2, B-T 5, S-C 3, C-T 4, B-C 1. Cheapest-crossing starts at S and takes S-A 2, then A-B 2 as the cheapest edge leaving {S,A}, then B-C 1, and finishes with C-T 4. That tree costs 9. Nearest-first from S keeps S-A 2, A-B 2, S-C 3 and C-T 4, which costs 11. One tie has to be called out loud there: B lands at 4 through A 2 + 2 and at 4 through C 3 + 1 alike, and the dial settles the tie for the vertex it discovered first, which is A.

The two trees differ by exactly one edge. The spanning tree holds B-C 1 where the shortest-path tree holds S-C 3, and that single swap is the whole difference between 9 and 11. Now try to travel the cheaper one. Follow the spanning tree's arrows back from C and you walk S-A-B-C 2 + 2 + 1 = 5. The shortest-path tree reaches C for 3. Same graph, same arrows, two different meanings: cheapest to build is not cheapest to travel.

So why is the one character legal at all? Draw a line that splits the vertices into two groups, and pick the cheapest edge crossing it. That edge belongs to some minimum spanning tree, wherever you drew the line. Check it four times. {S} against the rest is crossed by S-A 2 and S-C 3, and the cheaper one, S-A 2, is in the tree. {S,A} against {B,C,T} is crossed by A-B 2 and S-C 3, and A-B 2 is in the tree. {S,A,B} against {C,T} is crossed by B-C 1, S-C 3 and B-T 5, and B-C 1 is in the tree. {T} against the rest is crossed by C-T 4 and B-T 5, and C-T 4 is in the tree. Four lines, four hits.

That claim needs no condition, and it is the beautiful half. The condition shows up only when you ask a narrower question: is this pulsing edge a legal next move for the half-built tree in front of you? It is not, if the line you drew already has one of your committed edges crossing it. Take {S,C} against {A,B,T}, which cuts S-A after you have committed S-A. The cheapest crossing edge there is still B-C 1, and B-C 1 is still in the tree, so the theorem stands. It just tells you nothing about what to add next.

The proof of the unconditional claim needs two facts about trees, and only those two are new. Add one edge to a tree and exactly one cycle appears, because the tree already held a unique path between those two ends. That cycle left your side of the line, so it has to come back, which gives a second crossing edge no cheaper than the one that pulsed. Delete that second edge and the total cannot rise. That is the exchange argument from two pages back, run on a cycle instead of a schedule. The last setting on the dial, global-cheapest, sorts all six edges before it makes a single decision, roughly 6 × log₂6 ≈ 16 comparisons. Then it takes B-C 1, S-A 2 and A-B 2, skips S-C 3 because S, A, B and C are already joined to each other, and finishes with C-T 4. Same tree, same 9, from a different line: component against rest, not tree against rest. And this is the second departure promised on the first screen, so collect it now. It has no source, no frontier, and no unseen bucket, because every edge was visible from the first instant. It never stands anywhere, so it has no far end to look toward — which is why it is not a policy about where you are, and why the cut rule rather than the three buckets is what makes it legal. Go and drag the line for yourself now, and watch which lines grey out and why.

Hold onto that line. You just proved a global fact about every tree the graph admits by dragging one line through the vertices, and the last policy on this page proves its global fact by drawing the same line. So the fourth of the hinge's four comes loose here: the edges themselves. Name the discontinuity before crossing it, because it is real. Every policy so far bought permanence one step at a time, and this one settles nothing at any step, which is precisely what lets it be wrong early and recover. The same widget carries it in a second mode, and it needs one setup sentence. A flow obeys two rules: no edge carries more than its capacity, and every vertex except the two ends passes on exactly what it receives. Give each edge a partner pointing the other way, carrying whatever you have already pushed along it. Sending flow along that partner looks like cheating, so watch it once and the feeling goes. It is a reroute, not an undo.

Push badly on purpose. Capacities are S→A 10, A→B 3, B→T 3, S→C 10, C→T 2, B→C 4. The path S→A→B→C→T carries min(10,3,4,2) = 2, and S→A→B→T carries min(8,1,3) = 1, so the flow reads 3. Now S→C→T is blocked, because C→T is full at 2. Take S→C, then backwards along B→C, which is carrying 2, then B→T, and push 2 more. The flow reads 5. The 2 units that went B→C→T now go B→T, and C takes its 2 straight from S. Nothing was manufactured and the total only rose.

The path itself is found by the blind search you already own, run on the graph with those partner edges added, which is the only reason this policy fits on a page with one verb. It stops when the search stalls. Flood everything still reachable from S and you get {S, A, C}, because A→B and C→T are both full and B→C carries nothing back. That set is a line through the graph. Across it, A→B 3/3 and C→T 2/2 are full going out, and B→C 0/4 is empty coming back, so the net across is 5, the flow you have. Both conditions carry weight, because any flow returning across that line would have handed the search a way through. The failure is the certificate, and it is drawn with the same line you were dragging a few minutes ago.

11The export, and what you can now do

Twice now a global fact has been certified by one local object, which is enough instances to name it. The cheapest crossing edge belongs to some minimum spanning tree. That is a claim about every tree the graph admits, settled by looking at one edge. The saturated split certified a maximum flow, and it is one line drawn through the vertices. Neither proof walked the graph. So here is the thing worth carrying off this page: a global claim needs only a local certificate. You never have to inspect every candidate, as long as some small object must appear whenever the global thing is true.

Now spend that somewhere with no graph in it at all. Given 40 line segments drawn on a page, do any two of them cross? The obvious answer compares every pair, and for 40 segments that is 40 × 39 / 2 = 780 comparisons, all of them actually performed. The count is quadratic, so 400 segments would cost 79,800, and a million is not worth writing down. So ask the question you just learned to ask. Does a crossing have a local precursor — some small thing that must show up first?

It does, and finding it means holding two objects and never letting them merge. The first is a schedule ordered by x, holding every segment's left end, every right end, and every crossing, in the order a vertical line would meet them. The second is a stack of segments ordered by y, which is who sits above whom right now along that line. The certificate is a fact about the second object only. Two segments cannot swap their y-order without first being adjacent in it, so a crossing announces itself as an adjacency one moment before it happens. Name the wrong version too, because it is the one most likely to get quoted later. Sorting the segments by x and comparing adjacent pairs is not this algorithm and does not work: two segments can sit far apart in x-order and cross anyway. The adjacency that matters lives in y, and the schedule in x only says when to look.

So drag one segment across the other, and watch the stack rather than the picture. Segment P runs from (0,0) to (10,10), and segment Q runs from (0,4) to (10,2). At x = 0 the stack reads Q above P, and at x = 10 it reads P above Q. Somewhere between them they were neighbours. Solve for where. P has y = x and Q has y = 4 − 0.2x, so 1.2x = 4 and x = 3.33, at height 3.33. That crossing is an event the schedule inserts, and the adjacency existed the step before it. Beside the sweep, a counter prints what you are not doing. An insertion makes at most two new y-adjacencies, a deletion at most one, and a swap at most two. So 40 segments with 5 crossings give 2 × 40 + 5 = 85 events, and at most 130 neighbour tests 40 × 2 + 40 × 1 + 5 × 2 against 780 pair comparisons — a factor of 6 here, and unbounded as the count rises.

Climb back down the page and count what you are carrying. Breadth-first search, depth-first search, the dag sweep, Bellman-Ford, Dijkstra, Prim, Kruskal, Floyd-Warshall, augmenting-path max-flow. Nine famous names went past, and you never needed nine. Seven of the policies fall out of one generator: three buckets, plus a reason for moving a vertex into the third. Kruskal comes from a second generator, the cut rule, because it has no source and no frontier and never stands anywhere at all. Floyd-Warshall comes from a third. Change what you index by, from vertices to permissions, and the data structures evaporate. Three generators is a stranger claim than one, and unlike one it happens to be true.

You can also name the exact inequality each policy spends, which is what lets you build the counterexample yourself instead of remembering a prohibition. FIFO spends every edge costs one. Nearest-first spends the rest can only add weight. A rule you memorised predicts nothing, but a clause you can point at can be attacked with a slider. You hold two opposite repairs as well. When the structure already supplies a safe order, delete the machinery, since a dag needs no heap and negative weights stop mattering. When it does not, retune the world until the fast policy is legal, at a cost of one slow run of 63 relaxations, paid once and spent on all eight fast ones. And when a build system prints a circular-dependency error, you can say back edge and mean it.

All of that is one question standing where nine names used to stand: what is this order's reason, and what breaks it? The fraction gains its fifth entry, and this entry is unlike the four before it. The numerator is the information the answer needs. The denominator is what one probe returns, which is one vertex's neighbours and nothing else. You cannot ask for less than the answer, and a probe returns what a probe returns. Neither half of the fraction moves, so the only lever left is the order in which you spend the denominator.