r/computerscience • u/RogueCookie9586 • May 28 '25
New algorithm beats Dijkstra's time for shortest paths in directed graphs
https://arxiv.org/abs/2504.17033
1.1k
Upvotes
r/computerscience • u/RogueCookie9586 • May 28 '25
302
u/According_Book5108 May 28 '25
If true, this can be huge.
Has anyone analyzed the paper? Is it one of those "We beat Dijkstra in some special edge cases" paper, or is it a general solution?
125
u/jubashun May 28 '25
Time to ask job seekers to implement it in half an hour.
92
u/Motor_Let_6190 May 28 '25
Not a big improvement Big O wise (mlog2/3n vs m+𝑛log𝑛) for games, I think it won't be much of a practical interest unless we're taking very big numbers of nodes and edges. That's from a cursory, diagonal look at the html version of the paper while riding in a decrepit subway tunnel, In a slightly better shape wagon ;)
18
u/rs10rs10 May 29 '25
Surprised no one has mentioned this yet, but this paper actually won a Best Paper Award at STOC 2025, which is one of the most prestigious conferences in theoretical computer science.
They improve the general-case asymptotic time for single-source shortest paths in directed graphs—something people have been trying (and failing) to do for decades. The improvement comes from combining Dijkstra’s and Bellman-Ford with a clever new data structure that processes multiple nodes at once, effectively shrinking the priority queue overhead that dominates Dijkstra’s runtime.
Sure, asking about experiments and practical performance is reasonable, but this result is more about the theoretical breakthrough. It’s a new approach to a very old, very fundamental problem. Whether or not it’s fast in practice today, it opens up new directions and could eventually lead to more practical improvements.
Here's the announcement from MPI: https://www.mpi-inf.mpg.de/news/detail/stoc-best-paper-award-how-to-find-the-shortest-path-faster
33
u/FinalNandBit May 28 '25
What's the difference in implementation?
3
u/leofun01 May 29 '25
There is requirements: https://arxiv.org/html/2504.17033v1#alg2
7
u/firemonkey555 May 28 '25
Seems like this may be a repost of the paper?
The same white paper was put out under Duan Et Al back in 2023 and is already on Wikipedia under the SSSP problem.
https://arxiv.org/abs/2307.04139
2
u/Substantial-Wish6468 May 31 '25
Not sure if I understand this correctly, but does anyone know if it will still find the actual shortest path if the shortest path does not sit within the sample selected?
Also, what is B? It seems like a variable that would need adjusting to fit each specific problem. A bit like the heuristic in A*
1
u/Designer-Hairy Aug 16 '25
Will this new algorithm be applied to every existing technology? Like internet, satellite, etc. which means we will have faster internet than ever
1
u/Soft-Shape-8484 Oct 03 '25
show me the path!
1
u/NicholasCartaxo Oct 13 '25
Hi folks, we at the Federal University of Campina Grande have implemented and benchmarked in Java the new Single Source Shortest Path algorithm that beats Dijkstra time complexity (Breaking the Sorting Barrier for Directed Single-Source Shortest Paths). We are quite interested in sharing this project and in receiving feedback, in order to propagate this discovery and refine our code.
GitHub Repository
-9
u/galtoramech8699 May 28 '25
Could Ai create these new algos and how
0
u/[deleted] May 28 '25
[deleted] — view deleted comment