First, 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 · 2h ago
Very 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 · 29m ago
in the real world djikstra will definitely be faster.
polytely · 5h 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
RobRivera · 3h ago
Gamedevs -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 · 2h ago
Isn'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.
colonCapitalDee · 24m ago
This algorithm is asymptotically faster than the state of the art, but it isn't faster in practice. At least not yet!
RobRivera · 47m ago
That's what I have found to be the case: time is in short supply
hinkley · 3h ago
Maybe someone did and just didn’t see it as novel?
ljlolel · 6h ago
Tarjan was my algorithms professor. He invented many of them
larodi · 4h ago
…invented many of them algorithms? like which?
teraflop · 2h ago
Aside 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.
I'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.
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 · 3h ago
log^2/3 might be the weirdest component I’ve ever seen in a complexity formula.
jojomodding · 1h ago
I'm continually amazed by the asymptotic complexity of union-find, which is O(alpha(n)), where alpha(x) is the inverse of the Ackermann function (and n the number of sets you union). In other words, O(6) or so as long as your inputs fit into the observable universe.
hinkley · 1h ago
There's definitely a divide on who sees what sort of algorithms. The subject of this article is in Graph Theory space, which a lot of us get even without trying (I dabbled in TSP for a while because it's a difficult distributed programming problem and I wanted to explore the space for that reason).
But if you're not implementing AI or game engines, some of the linear algebra space may be a road less traveled.
bawolff · 2h ago
I still think matrix multiplication's O(n^2.371339) is super weird.
adgjlsfhk1 · 2h ago
Matrix multiplication definitely should be O(n^(2+o(1))).
adgjlsfhk1 · 2h ago
for 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.
Sniffnoy · 1h ago
Hey the asterisks in your reply got read as formatting so it's ended up messed-up.
adgjlsfhk1 · 1h ago
oops. fixed.
hinkley · 1h ago
Are BigInteger multiplications in logn² now or do they still have weird terms in them?
adgjlsfhk1 · 1h ago
down to nlogn
ape4 · 5h ago
Sounds a lot more complicated that Dijkstra. But I guess that's the way it goes.
larodi · 4h ago
Dijkstra 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 · 4h ago
Dijkstra _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 · 2h ago
For 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 · 1h ago
I think you could do it with many board games. Mouse Trap for monads? Poker for permutations? Dice for decision theory?
cantor_S_drug · 5h ago
reminds me of TimSort.
crawfordcomeaux · 2h ago
I wonder if hybridizing this with selective use of randomness to probe beyond frontiers leads to another speedup.
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.
> “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
Rather than the academia.
Just a hunch tho
His Turing award writeup gives a pretty broad overview of his research contributions: https://amturing.acm.org/award_winners/tarjan_1092048.cfm
https://en.wikipedia.org/wiki/Splay_tree
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.
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.
But if you're not implementing AI or game engines, some of the linear algebra space may be a road less traveled.
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.