The Macclesfield projectBidirectional Dijkstra on Macclesfield's streets: 400 trips, counted
The same route, found two ways, with a tally of how many points each search had to settle.
One request to the Overpass service returns every public road that OpenStreetMap holds in a box around Macclesfield: 246.1 km of road segments. In Python the learner turns them into a graph, keeps the largest connected network of 11,974 mapped points, and gives each segment its length as a cost. To keep the first version simple, every street is treated as two-way and the cost is distance, not time. Then 400 random pairs of points are drawn and each pair is solved twice.
400 random trips on the Macclesfield street graph, our Python run on OpenStreetMap data| Measure | One-way Dijkstra | Bidirectional Dijkstra |
|---|
| Points settled, median trip | 6,252.5 | 3,536 |
| Points settled, all 400 trips | 2,423,317 | 1,387,810 |
| Trips where it settled fewer points | 25 (6.2%) | 375 (93.8%) |
| Same shortest distance as the other method | 400 of 400 | 400 of 400 |
The typical trip was 3.39 km long. On a typical trip the two-ended search settled 55% of the points that the one-ended search needed (a median ratio of 0.554), and across all trips it did about 43% less work. It was not a clean win every time: on 4.2% of trips it settled over a tenth more points than the ordinary search. The distances, though, matched on all 400 trips. That depends on the stopping rule. It is tempting to stop the moment the two ripples first touch, but the first meeting point is not always on the shortest route. The correct rule keeps going until the two frontiers, added together, are at least as long as the shortest complete route found so far.
Work ratio by route length (bidirectional points settled divided by one-way), median of each group, our calculation| Shortest route length | Trips | Median ratio |
|---|
| Under 1.5 km | 58 | 0.506 |
| 1.5 km to 3 km | 107 | 0.516 |
| Over 3 km | 235 | 0.579 |
Why roughly a half? A ripple on a flat map covers an area that grows with the square of its radius. One circle of radius r has area pi r squared; two circles of radius r over 2 have half that in total. Short trips in the middle of the network land almost exactly on the prediction. Long trips save a little less, because a ripple that has already reached the edge of the mapped box has nothing more to explore there, which flatters the one-way search.
Ages 8 to 11
Two pupils solve a paper maze from opposite ends and count the squares they each coloured.
Ages 11 to 15
Code one-way Dijkstra in Python on a small grid and print the number of points it settled.
Ages 15 and up
Add the backward search and the stopping rule, then run the 400-trip comparison on the real graph.
Map data and its limits
Road data is © OpenStreetMap contributors, available under the Open Database Licence. The graph, the trips and the counts are ours. The network stops at the edge of our box and ignores one-way rules and speed limits, so these figures describe the exercise, not real journey times.
