5 ms·
Breaking the sorting barrier for directed single-source shortest paths
https://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033
- ljlolel 1y agoTarjan was my algorithms professor. He invented many of them
- larodi 1y ago…invented many of them algorithms? like which?
- kzrdude 1y agoMaybe Tarjan's strongly connected components. That's one I've implemented at some point at least.
- larodi 1y agoThanks, this is interesting, how could I miss an important algorithm related to graphs, incredible.
- bob1029 1y agoThis is one of my favorites: https://en.wikipedia.org/wiki/Splay_tree https://en.wikipedia.org/wiki/Splay_tree
- teraflop 1y agoAside from inventing a bunch of individual algorithms, Tarjan is also known for introducing various theoretical techniques that are now considered fundamental. Most notably, amortized analysis. His Turing award writeup gives a pretty broad overview of his research contributions: https://amturing.acm.org/award_winners/tarjan_1092048.cfm https://amturing.acm.org/award_winners/tarjan_1092048.cfm
- deleted 1y ago[deleted]
- polytely 1y ago> But curiously, none of the pieces use fancy mathematics. > “This thing might as well have been discovered 50 years ago, but it wasn’t,” Thorup said. “That makes it that much more impressive.” this is so cool to me, it feel like a solution you could* have stumbled upon while doing game development or something *probably wouldn't but still
- hinkley 1y agoMaybe someone did and just didn’t see it as novel?
- kevingadd 1y agoDepending on where you work they might not let you publish a paper about it. Certainly was the case at one game studio I worked for, very secretive.
- RobRivera 1y agoGamedevs -I find at least- are so obsessively deep at SOLVING their problem at hand that their headspace is indexed on shipping the game, the project, deadlines, and what to eat for the next meal (probably pizza). Rather than the academia. Just a hunch tho
- 8n4vidtmkvmk 1y agoIsn't that just it though? The problem very well could be that some part of the game is running too slow so they just start solving it. No time to read and write academic papers.
- RobRivera 1y agoThat's what I have found to be the case: time is in short supply
- colonCapitalDee 1y agoThis algorithm is asymptotically faster than the state of the art, but it isn't faster in practice. At least not yet!
- ape4 1y agoSounds a lot more complicated that Dijkstra. But I guess that's the way it goes.
- cantor_S_drug 1y agoreminds me of TimSort.
- larodi 1y agoDijkstra is still very difficult for many and not universally taught in 7th grade even though you can arguably explain what a shortest path in a graph is to 14 y.o.
- GolDDranks 1y agoDijkstra _could_ be universally taught in 7th grade if we had the curriculum for that. Maybe I'm biased, but it doesn't seem conceptually significantly more difficult than solving first degree equations, and we teach those in 7th grade, at least in Finland where I'm from.
- crawfordcomeaux 1y agoFor sure! The main thing keeping us from teaching advanced things to younger folks is the seeming addiction to teaching poorly/ineffectively. I'm here to find the physical play-with-your-hands demonstrations needed for teaching kids as young as 5 the intuitions/concepts behind higher-order category theory without all the jargon.
- kevindamm 1y agoI think you could do it with many board games. Mouse Trap for monads? Poker for permutations? Dice for decision theory?
- hinkley 1y agoI think we forget how old the term algorithm is. We started this journey trying to automate human tasks by divide and conquer, not computers. Merge sort is supposedly invented in 1950, it’s more likely it was invented in 1050 than 1950. Sort a room full of documents for me. You have three minions, go.
- flafla2 1y agoO(m log^2/3 n) !!! What a triumph.
- supernetworks_ 1y agohttps://arxiv.org/abs/2504.17033 https://arxiv.org/abs/2504.17033 We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.
- hinkley 1y agolog^2/3 might be the weirdest component I’ve ever seen in a complexity formula.
- deleted 1y ago[deleted]
- bawolff 1y agoI still think matrix multiplication's O(n^2.371339) is super weird.
- adgjlsfhk1 1y agoMatrix multiplication definitely should be O(n^(2+o(1))).
- adgjlsfhk1 1y agofor about a decade, integer multiplication was at n4^log*(n) where log* is the iterated logarithm. Also the curently best factorization algorithm (GNFS) is at exp(k*log(n)^1/3log(log(n))^2/3). Intro algorithms classes just tend to stay away from the really cursed runtimes since the normal ones are enough to traumatize the undergrads.
- aDyslecticCrow 1y agoI'm intrigued but the article is very verbose with little detail. Mabie the paper will give a more satisfying description. Im most curiosity how the algorithm fulfil the "global minima" that djixtra guarantees. The clumping of front-tier nodes seem prone to missing some solutions if unlucky.
- o11c 1y agoFirst, note that this complexity is actually worse for highly dense graphs, where `m` (number of edges) dominates rather than `n` (number of nodes) [note that a useful graph always has `m > n`, and often `m <= 2d n`, where `d` is the number of dimensions and the 2 is because we're using directed edges. Ugh, how do we compare log powers?]. Additionally, the `n` in the complexity only matters if for the Dijkstra approach you actually need a frontier of size proportional to `n` [remember that for open-grid-like graphs, the frontier is limited is limited to `sqrt(n)` for a plane, and for linear-ish graphs, the frontier is even more limited]. Also note that the "sorting barrier" only applies to comparison-based sorts, not e.g. various kinds of bucket sorts (which are easy to use when your weights are small integers). Which seems to be part of what this algorithm does, though I haven't understood it fully.
- lqet 1y agoVery good points. I wonder what this means for real-world street network graphs. In my experience, m can be considered proportional to n in road network graphs (I would estimate m ≈ 2C n, with C being between 2 and 3). This would mean that the asymptotic running time of this new algorithm on a classic road transportation network would be more like O(Cn log^2/3 n) = O(n log^2/3 n), so definitely better than classic Dijkstra (O(n log n) in this scenario). On the other hand, the frontier in road network graphs is usually not very big, and (as you also said for grid graphs) you normally never "max out" the priority queue with n nodes, not even close. I would be surprised if the ^2/3 beats the additional constant overhead of the new approach in this case.
- adgjlsfhk1 1y agoin the real world djikstra will definitely be faster.
- mananaysiempre 1y agoIt’s not often that you see O(E + V log V) Dijkstra with Fibonacci heaps, either, the O((E + V) log V) version with plain binary heaps is much more popular. I don’t know if that’s because the constants for a Fibonacci heap are worse or just because the data structure is so specialized.
- crawfordcomeaux 1y agoI wonder if hybridizing this with selective use of randomness to probe beyond frontiers leads to another speedup.
- karussell 1y agoIt is somewhat funny that it took 12 submissions here on hackernews to bring it to a wider audience :) https://hn.algolia.com/?query="2504.17033" https://hn.algolia.com/?query="2504.17033"