alcinnz on Nostr: To beat the cost of sorting Duan, et al's algorithm takes advantage of the fact that ...

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