No Two Walked Together Twice

In 2008 a road-routing group reported a query answered in 154 microseconds on a Western European road network of some eighteen million nodes and forty-two million directed edges.

The search had settled 359 nodes and relaxed 1,159 edges to get there.

Those are excellent routing results. They are not evidence that the roads selected are independent of one another.

The distinction is easy to lose because a route with many edges looks dispersed. It crosses junctions, carriers, contracts, systems. The optimiser has made a great many local choices along the way.

But Dijkstra’s procedure asks a narrower question than it appears to. It extracts the least tentative distance, settles that vertex, relaxes its outgoing edges, and stops when the target comes off the queue. The objective is cumulative path cost, and nothing else is in it.

A shared insurer or clearing dependency is invisible unless somebody has already put its cost into the graph. The same holds for a set of routes. Several cheapest paths can be entirely different on the map and identical where failure matters.

Fisher made balance a condition, not a finding #

Ronald Fisher went to Rothamsted in 1919 to work on its accumulated field experiments, and the problem there was never finding a low-cost route through a field. It was making treatment comparisons survive the field’s own nuisance structure.

A Latin square assigns treatments so that every row and every column sees each treatment exactly once. Soil gradient and planting time are then separated from treatment effect without either being modelled directly.

The arrangement does not discover balance in the outcome. It puts balance into the assignments, before anything is grown.

The balanced incomplete block design sharpens the condition. When a block cannot hold every treatment, every pair of treatments must still occur in a common block the same number of times. Fisher’s inequality came out of the practical question of how few blocks could preserve that pairwise guarantee. That is a different kind of efficiency from the routing kind. It does not assume more blocks mean more comparison. It counts which treatments meet.

Kirkman made repetition impossible by rule #

Kirkman’s 1850 puzzle asks for fifteen schoolgirls to walk in rows of three for seven days, with no two of them walking together twice. The solution arranges thirty-five triples into seven parallel classes of five.

The seven days are not decoration on the puzzle. Each parallel class covers every girl exactly once, and the no-repeat rule applies to pairs rather than to the fact of being assigned a row at all.

A timetable that puts every girl somewhere every day can repeat the same pair all week.

Room squares carry the constraint into round-robin scheduling: every unordered pair occupies exactly one cell. The schedule is fair because pair coverage is part of the object being constructed, not because the tables look well used. That is the missing column in a supplier network reporting route counts. Suppliers can carry different legal names, different contracts and different operational hops while their routes converge on one port or one insurer. Model vendors can look like independent confirmation while their features descend from a single upstream source. A lowest-cost execution route can cross the same clearing dependency every time it leaves its own neighbourhood.

The count that matters is not routes. It is unique pairings and shared upstream nodes.

Dijkstra and Prim make different promises #

The two algorithms look nearly identical in operation. Both use a priority queue, extract a minimum, and expand from what has already been accepted. The difference is what the key holds.

Dijkstra orders by cumulative distance from the source. Prim orders by the cheapest edge joining a new vertex to the growing tree. The outputs differ accordingly. Dijkstra returns a shortest path or a shortest-path tree. Prim returns a minimum spanning tree. Neither is a balanced design, and neither has ever claimed to be. Calling either output diversified adds a claim its objective function does not contain.

A routing report therefore needs two certificates rather than one.

The first is the path, reconstructed from parent pointers and summed independently of the algorithm’s own bookkeeping. That tests whether the reported total is the sum of the reported edges. The second is an incidence record: selected routes set against the dependencies they use. That tests whether different-looking paths have been paying the same dependency the whole time.

Where the network starts reacting #

Fisher’s plots do not rewire themselves after allocation. Kirkman’s schoolgirls do not change which triple is cheapest halfway through the week. A block design fixes its assignments and then observes what happens.

A live network has capacities, failures and prices. A route changes usage, usage changes cost, and cost changes the next route. The dependence can therefore be produced by the optimisation rather than sitting there as a fixed defect waiting to be counted. A balance constraint can expose concentration. It cannot describe traffic that responds to its own exposure.

None of which is a reason to go back to counting routes. It is a reason to keep the design condition and the graph objective in separate columns.

Kirkman’s rule is not that every girl walks every day. It is that no two of them ever walk together twice, and the second is a great deal harder to satisfy than the first.

A route report counts the walks.

The pair table is what says whether the week was actually different, and no shortest-path objective will ever produce one.