4 ms·
A New Algorithm Makes It Faster to Find the Shortest Paths
- demarq 1y agoHere is the paper https://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033
- kasperni 1y agoWhy not post the original story instead. https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/ https://www.quantamagazine.org/new-method-is-the-fastest-way...
- atum47 1y agoThank you. The op was so full of ads i couldn't even read it.
- hypertele-Xii 1y agoOnly within undirected graphs. Sadly, this won't revolutionize video games, where we still have to use the A* algorithm from 1968 that is the literal computing bottleneck limiting us to mere hundreds of intelligent characters at once in a barely dynamic environment. I got way too excited.
- CMay 1y agoIn the article it does talk about how they arrived at a partial solution that only worked on undirected graphs, but then they started taking a hybrid approach to get it to work on directed graphs. The paper also indicates it works on directed graphs: https://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033 That said, it might only be faster for large, sparse graphs.
- seniortaco 1y agoJump point search is obscenely fast. It's technically an optimization of A* but the behavior and runtime looks nothing like it.
- mecsred 1y agoIt only worked on undirected graphs in 2023. This article is about the newest breakthrough that works on directed graphs as well.
- mellosouls 1y agoDiscussed here a couple of months ago: https://news.ycombinator.com/item?id=44812695 https://news.ycombinator.com/item?id=44812695
- quapster 1y agoSorry, didn't see that post when searching!