4 ms·

Move over Dijkstra: New algorithm just rewrote 70 years of computer science

37 points by robaato 1y ago

robaato 1y ago
https://archive.is/M9fyh https://archive.is/M9fyh
robaato 1y ago
Original paper: https://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033
- yorwba 1y ago
  Previous discussion: https://news.ycombinator.com/item?id=44812695 https://news.ycombinator.com/item?id=44812695
  - tomhow 1y ago
    Thanks! Breaking the sorting barrier for directed single-source shortest paths - https://news.ycombinator.com/item?id=44812695 https://news.ycombinator.com/item?id=44812695 - Aug 2025 (51 comments)
swiftcoder 1y ago
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
- n4r9 1y ago
  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.
nicholasbraker 1y ago
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.
- kstrauser 1y ago
  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.
n4r9 1y ago
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 https://dlnext.acm.org/doi/10.1016/0167-6377%2887%2990053-8 [1] https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies [2] https://project-osrm.org/ https://project-osrm.org/ [3] https://www.graphhopper.com/ https://www.graphhopper.com/
- DennisL123 1y ago
  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.
  - n4r9 1y ago
    Hi! If I remember rightly, you can run contraction hierarchies but stop short of the full contraction, and use the core vertices as "hubs"? Hope you don't mind but I took a little look at your posting history and saw this: https://news.ycombinator.com/item?id=41954120 https://news.ycombinator.com/item?id=41954120 I've been researching this lately, as we've recently implemented traffic patterns in our routing model and are just now working on live traffic updates. The easiest way to adapt our existing code looks like Customizable Contraction Hierarchies. There's a really nice review paper here: https://arxiv.org/abs/2502.10519 https://arxiv.org/abs/2502.10519 . The technique is to apply nested dissections to build a "metric-independent" hierarchy based purely on connectivity, which gives a decent quality of contraction regardless of transit times. Is that what you mean by decomposing the network into "cells"?

37 points by robaato 1y ago

robaato 1y ago

https://archive.is/M9fyh https://archive.is/M9fyh

robaato 1y ago

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

yorwba 1y ago
Previous discussion: https://news.ycombinator.com/item?id=44812695 https://news.ycombinator.com/item?id=44812695
- tomhow 1y ago
  Thanks! Breaking the sorting barrier for directed single-source shortest paths - https://news.ycombinator.com/item?id=44812695 https://news.ycombinator.com/item?id=44812695 - Aug 2025 (51 comments)

swiftcoder 1y ago

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

n4r9 1y ago
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.

nicholasbraker 1y ago

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.

kstrauser 1y ago
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.

n4r9 1y ago

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 https://dlnext.acm.org/doi/10.1016/0167-6377%2887%2990053-8 [1] https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies [2] https://project-osrm.org/ https://project-osrm.org/ [3] https://www.graphhopper.com/ https://www.graphhopper.com/

DennisL123 1y ago
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.
- n4r9 1y ago
  Hi! If I remember rightly, you can run contraction hierarchies but stop short of the full contraction, and use the core vertices as "hubs"? Hope you don't mind but I took a little look at your posting history and saw this: https://news.ycombinator.com/item?id=41954120 https://news.ycombinator.com/item?id=41954120 I've been researching this lately, as we've recently implemented traffic patterns in our routing model and are just now working on live traffic updates. The easiest way to adapt our existing code looks like Customizable Contraction Hierarchies. There's a really nice review paper here: https://arxiv.org/abs/2502.10519 https://arxiv.org/abs/2502.10519 . The technique is to apply nested dissections to build a "metric-independent" hierarchy based purely on connectivity, which gives a decent quality of contraction regardless of transit times. Is that what you mean by decomposing the network into "cells"?