The Leighton Buzzard projectPrepare the map once, then every search is small
One road network, a thousand journeys, and two ways of answering them.
The learner downloads every road in a box around the town from OpenStreetMap in one query, from the A roads down to service roads: 3,008 pieces of road, 305.0 km in total. Keeping only junctions and road ends, and joining the stretches between them, leaves a network of 4,689 points and 5,040 links in its largest connected part. One-way rules are ignored to keep the first version simple. The program then picks 1,000 random pairs of points and finds the shortest road distance between each pair. The average trip is 3.27 km and the longest 9.74 km.
Dijkstra's algorithm, stopping the moment it reaches the destination, has to settle 2,399.8 junctions on average for each journey, about half the whole map, because it spreads outwards in every direction until it arrives. Then the learner builds a contraction hierarchy. Junctions are removed one at a time, least important first. Whenever removing one would break the shortest route between two of its neighbours, a shortcut is added between them, but only after a small local search, the witness search, fails to find another route that is just as short. At query time, the search runs from both ends and only ever climbs towards more important junctions.
1,000 random journeys on the Leighton Buzzard road network, our Python run| Method | Shortcuts added | Preparation | Junctions settled per journey | Distances correct |
|---|
| Dijkstra from scratch | none | none | 2,399.8 on average | reference |
| Hierarchy, careful order | 3,552 | 0.9 seconds | 44.0 on average, 74 at most | 1,000 of 1,000 |
| Hierarchy, random order | 30,434 | 727.5 seconds | 582.7 on average | 1,000 of 1,000 |
With a careful order, which removes first the junctions that need the fewest new shortcuts, each search settles 44 junctions instead of about 2,400, and every one of the 1,000 answers matches Dijkstra to the metre. The same method with the junctions removed in random order is still correct, but it adds 30,434 shortcuts, takes over twelve minutes to prepare, and its searches settle 582.7 junctions. The algorithm was the same both times; only the order changed. The last junction to be removed, and so the most important one by this measure, joins Lake Street, Stanbridge Road and Leckbridge Court.
Ages 8 to 11
On a paper map, remove a village and draw the direct lines its roads imply between neighbours.
Ages 11 to 15
Write Dijkstra in Python with a priority queue and count how many places it visits.
Ages 15 and up
Build the hierarchy, then change the contraction order and measure what it costs.
Sources and limits
Roads are from OpenStreetMap contributors under the Open Database Licence, read with a single Overpass query on 1 October 2026. Contraction hierarchies come from the work of Robert Geisberger and colleagues, published in 2008. The network, the shortcut counts and every timing are ours, from ordinary Python on one computer, and one-way streets were deliberately left out.
