The Sorting Barrier: Why Plow Routing Still Runs on a 1959 Algorithm

Every route PlowPath plans rests on one question, asked thousands of times: how far is it, by road? Since 1959 the answer has come from Dijkstra's algorithm. In 2025 it was finally beaten on paper, and in 2026 a team of AI agents went further and proved it. Here is what that means, on the gallery's own streets.

Greg Dogum · 2026-10-06

Before a solver can decide which truck should take which street, it has to know how far everything is from everything else, by road, obeying every one-way sign. Not once: thousands of times, every time it weighs a move. On the pipeline page this is stage 08, distance mapping, and it is answered the way almost every routing system has answered it for sixty-seven years: with Dijkstra's algorithm.¹

In 2025, for the first time in four decades, someone proved there is a faster way.² In September 2026 a team of AI agents pushed the result further and checked the proof by machine.³ This essay is about what that means for a town's snow routes. The figures run live in your browser, on the same road networks as the gallery. The short answer is that Dijkstra still wins at town scale. The interesting part is why.

One question, thousands of times

Dijkstra's idea is a wavefront. Start at the depot. Of all the intersections you have reached but not finished, take the nearest, call it finished, and look down each street leaving it to see whether that offers a shorter way somewhere else. Repeat until nothing is left. Because you always finish the nearest intersection first, nothing finished can ever be improved, and the distances come out exact.

There are other ways to grow the wavefront. Band relaxation, known as Δ-stepping,⁴ finishes everything inside the next band of distance at once, in no particular order. Wide bands need fewer rounds but redo more work; a band of zero width is Dijkstra again. Race them here:

Interactive figure 1: Dijkstra and band relaxation (Δ-stepping) race on a real gallery town's road network, with the order each hands intersections back.

Both finish with exactly the same distances; they differ in the order they get there. Look at the ribbons under each map. Dijkstra's is a smooth gradient, near to far, because it has to be: it hands back every intersection in exact distance order. The band's ribbon comes in batches, and inside a batch the order is arbitrary.

Why it is called a barrier

Handing back n things in sorted order is sorting, and sorting by comparison costs about n log n. With the Fibonacci heap of 1984,⁵ Dijkstra's running time is O(m + n log n): it reads each of the m street segments once, and pays log n for each of the n intersections it finishes. That n log n is the sorting barrier.

It held for forty-one years, in this setting at least: directed networks, real-valued lengths, an algorithm that only compares and adds. Neighbouring settings gave way sooner, to linear time for undirected networks with whole-number lengths in 1999⁶ and to a randomized method for undirected networks with real lengths in 2023.⁷ In 2024 it was even shown that, with the right heap, Dijkstra is the best possible algorithm at the job of listing vertices in distance order.⁸ The loophole is in the job description. An algorithm that does not insist on producing that order is not bound by it, and the band in figure 1 already hints at how: finish a whole group without sorting inside it.

Sixty-seven years of one exponent

Every bound in this story fits one picture. Give the network an average of d streets per intersection, write that density as d = logᵅ n, and divide each running time by n. What is left is log n raised to some power, and the smaller the power, the faster the algorithm. Road networks sit at the far left, α near zero: two or three streets per corner, whatever the size of the town.

Interactive figure 2: The history of single-source shortest-path bounds from 1959 to 2026, as the exponent of log n per vertex against network density.

The 2025 algorithm of Duan, Mao, Mao, Shu and Yin was the first to go under the line for directed graphs with real weights.² It works in a bounded recursion that never sorts the whole frontier: a few rounds of the older Bellman–Ford relaxation shrink the frontier to a handful of pivots, and only those go into a priority queue. A 2026 follow-up by the same group lowered the exponent again.⁹

Then, in September 2026, Vals AI reported C-HD: a new algorithm designed by a team of AI agents coordinating on a message board over about fifteen hours, with its correctness and its running time proved in Lean, a language for machine-checked mathematics.³¹⁰ It holds the record across the middle of the chart, the band where the 1984 Fibonacci heap had been best for forty years.

Anatomy of the new bound

C-HD's running time, with n intersections and m street segments, is

O( n + m + m · log(2 + m/(n+1)) + m^1/3 · (n log n)^2/3 )

Three terms: read the graph once; a per-segment cost that grows slowly with density; and a blend of m and n log n that sits between them. The proof only covers sparse enough graphs, m ≤ n·⌊⌊log₂n⌋^3/4⌋, and outside that range, and for small inputs, the verified program runs Bellman–Ford instead.³ Move the sliders, or load a real network:

Interactive figure 3: The three terms of C-HD's bound for a chosen network size and density, with every competing bound ranked at that size.

On a road network the cube-root term leads, which is the regime the bound was built for. But notice the table: at the size of a gallery town, with constants set to 1, the 1984 formula is still smaller.

Inside C-HD

Here is the machinery, on about thirty real intersections. Each call takes a frontier and runs one small, bounded search out of each frontier intersection, stopping once it has discovered k of them. Intersections it touches but cannot improve still count toward that limit, as unexplored leaves. A search that hits the limit becomes a tree whose root is kept as a pivot; a search that runs dry finishes its little patch on the spot. Edges that can never help again are deleted for good. Only pivots enter the priority queue, and the recursion does the rest in batches.

Interactive figure 4: A runnable, scaled-down model of C-HD stepping through about thirty real intersections of a gallery town, checked against Dijkstra.

Step through it, or jump to each mechanism. Every run is checked against Dijkstra and matches; in this site's tests the model matches it on more than a thousand random graphs and on real corners of three gallery towns.

How big before it pays?

The writeup's own example takes n = 2¹⁰⁰⁰ along the profile where the bound shines: there, comparing leading terms alone, C-HD is about 1.78 times ahead.³ Keep every term, with constants set to 1, and it is still behind. Zoom out until it is not:

Interactive figure 5: Zooming out from a town's 170 intersections through the US road network to the astronomically large graphs where C-HD's full formula finally beats Dijkstra's.

And constants set to 1 flatter the new algorithms. The writeup is plain that the constants in the formal construction are "enormous, so this does not establish a practical speedup."³ An independent implementation of the 2025 algorithm found Dijkstra three to four times faster in every scenario tested, road networks of up to ten million vertices included, and estimated the new method would need graphs of more than 10⁶⁷ vertices to pull ahead.¹¹

Who wins where

Put every size and density on one map, and pin every town in the gallery on it:

Interactive figure 6: Which shortest-path bound is smallest at each network size and density, with every gallery town and the US road network marked.

The gallery sits in the far lower-left corner: a few hundred to a few thousand intersections, two to three streets each. There, the smallest formula is Fibonacci-heap Dijkstra or Duan 2025, and C-HD's is 15 to 46 percent behind. Only out at the size of the whole US road network, about 24 million intersections,¹² does C-HD's formula come out smallest, and that is before its constants.

Race them yourself

Formulas are one thing; here is a stopwatch. These are the textbook algorithms, on the gallery's own road networks, in your browser:

Interactive figure 7: A live benchmark of Dijkstra, Δ-stepping, Bellman–Ford and breadth-first search on gallery road networks, checking at every start that the weighted algorithms match Dijkstra and that breadth-first search reaches the same intersections.

On an ordinary laptop, one Dijkstra search on Oberlin, Ohio, finishes in microseconds, and on Duluth, the gallery's largest town, in around half a millisecond. Much of that time is memory: fetching the next street from wherever it lives. Even breadth-first search, which has no log n to pay, slows per edge as the towns grow. The log n that the new algorithms shave off is real, but it is one cost among several, and at this size every algorithm in the race finishes long before a screen can redraw.

What this means for a snow route

PlowPath's route solver answers its distance questions with Dijkstra and a binary heap, run once from each intersection the solver asks about and remembered after, so every later question from the same corner is a lookup. At town scale the wins worth having come from asking fewer questions, and from asking them of a well-laid-out graph, not from a faster answer to each one.

That is not a reason to look away. The sorting barrier stood for forty-one years, was broken in 2025, and has been pushed further twice since, the last time with a proof checked by machine. The research is moving faster than it has in decades, and the practical gap is a matter of constants, which is exactly the kind of gap engineering closes. When it closes, the first place it will show is stage 08 of the pipeline: the question asked thousands of times.

This essay grew out of an interactive explorer of the C-HD bound. Its algorithms and figures were rebuilt to run on the gallery's own road networks.

Open the gallery · Model your town · How the engine works