Discussion
About a year ago Duan, Mao, Mao, Shu, & Yin published a performance breakthrough in how to calculate a route between 2 points in a network. A breakthrough we've previously suspected to be impossible!
This is useful to me if I want to include street-maps in the feature-phone I'm planning to build, as it greatly simplifies the code I'd need to write in order for it to give you directions on how to get somewhere! Potentially enabling it to run on the cheap microcontroller I've ordered.
1/4?
The way it works involves recursively splitting the network up into smaller chunks by scouting ahead a finite distance, then stitching the results back together.
Once that subnetwork is small enough we can use our classic algorithms such as Dijkstra's, confident that we won't be considering too many intersections at once.
The trick is in stitching those results back together without cutting into the performance wins! For this we need clever datastructures.
2/3?
To beat the cost of sorting Duan, et al's algorithm takes advantage of the fact that splitting a subnetwork can only give you smaller distances, so it can prepend those results to a priority queue.
You can read the paper for yourself: https://arxiv.org/abs/2504.17033
Previously extensive preprocessing was done to streetmaps searching for shortcuts to be taken at runtime. Duan, et al's algorithm doesn't need that. It efficiently handles any network without ever being slow than Dijkstra's Algorithm!
3/3
Install bonfire.cafe
Get the full app experience
