Original paper: https://arxiv.org/abs/2504.17033

Anyone poked at this enough to see if it offers useful improvements at small scales? We use a ton of Dijkstra for various subproblems of pathfinding in video games, but the graphs don't tend to be huge (a few thousand nodes, maybe), or highly connected

The challenge of implementing this for internet routing is that you'll probably need a whole new protocol implementation as part of either BGP (currently the protocol responsible for Internet routing between networks) or something entirely new. Let alone that BGP is a path vector protocol and not a link-state protocol that uses Dijkstra (like OSPF and IS-IS).

It might optimize internal routing but getting this standardised across vendors etc. is not impossible, but probably takes a long time to standardise/govern etc.

The linked medium post is clearly written by an AI but I think it does a decent job at summarising the results. Glancing through the paper on ArXiv, it feels like they've cleverly combined speed-up techniques from variations of Dijkstra invented over the years.

The Thresh X2 [0] algorithm - for example - does away with the priority queue that is the bottleneck in Dijkstra. Instead, it iteratively runs a "label-correcting" routine over increasing search radii until the target is hit. I only learnt about this algorithm this year and can't find much about it online, although I've heard that it's sometimes used in videogames.

Then there's Contraction Hierarchies [1], used by many modern routing engines (such as OSRM [2] or GraphHopper [3]). This involves a slow pre-processing step in which nodes are put into a hierarchy of "importance", allowing a modified query-time routine which is orders of magnitude faster than Dijkstra. Recent work on this has also resulted in query-time routines that eliminate priority queues entirely. However, this assumes a fairly static road graph over which many requests are run.

In the linked algorithm, they seem to have an iteratively increasing radii and a routine which applies Bellman-Ford to identify "important" nodes. As I understand it, this decreases the number of nodes that need to be inserted into the priority queue.

[0] https://dlnext.acm.org/doi/10.1016/0167-6377%2887%2990053-8

[1] https://en.wikipedia.org/wiki/Contraction_hierarchies

[2] https://project-osrm.org/

[3] https://www.graphhopper.com/