Move over Dijkstra: New algorithm just rewrote 70 years of computer science
1–10 of 34 posts
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#2Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#3Original paper: https://arxiv.org/abs/2504.17033
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#4Original paper: https://arxiv.org/abs/2504.17033
Previous discussion: https://news.ycombinator.com/item?id=44812695
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#5Anyone 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
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#6The 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.
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#7Anyone 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
My hunch would be to stick with Dijsktra (or A*). There's a bunch of additional routines here which appear to improve behaviour as the number of nodes becomes large, but very likely lead to large coefficients in the complexity.
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#8The 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
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#9The 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 standa…
Why would that be? I don’t know how the version of sort() I use is implemented, but the results are the same as any other correct algorithm.
Re: Move over Dijkstra: New algorithm just rewrote 70 years of computer science
#10The 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-correc…
OSRM founder, here. Yes, you are right, many of the speedup techniques are related. My personal opinion is, tho, that looking at the identification of important nodes is best captured by the ideas of applying partitioning to multi-level dijkstra and by what’s called hub-labels. The latter has a close relationship to Contraction Hierarchies.