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.
polytely · 3h 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 · 49m 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 · 16m 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.
hinkley · 54m ago
Maybe someone did and just didn’t see it as novel?
aDyslecticCrow · 1h ago
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.
ljlolel · 3h ago
Tarjan was my algorithms professor. He invented many of them
larodi · 2h ago
…invented many of them algorithms? like which?
teraflop · 28m 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.
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 · 51m ago
log^2/3 might be the weirdest component I’ve ever seen in a complexity formula.
adgjlsfhk1 · 10m 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.
bawolff · 14m ago
I still think matrix multiplication's O(n^2.371339) is super weird.
adgjlsfhk1 · 9m ago
Matrix multiplication definitely should be O(n^(2+o(1))).
ape4 · 3h ago
Sounds a lot more complicated that Dijkstra. But I guess that's the way it goes.
larodi · 2h 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 · 2h 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.
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
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.
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
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.
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.