Show HN: C99 implementation of new O(m log^(2/3) n) shortest path algorithm (github.com)

I implemented the STOC 2025 Best Paper Award winner in C99. The algorithm achieves O(m log^(2/3) n) complexity, breaking the 65-year-old sorting barrier for sparse directed SSSP that Dijkstra established at O(m + n log n).

*Key implementation details:* - Cache-optimized CSR layout for maximum spatial locality - Zero-allocation design with pre-allocated workspaces - Recursive subproblem decomposition instead of global priority queues

*Benchmarks:* On graphs with 250k–1M nodes, this shows 20,000x+ speedups over standard Dijkstra implementations. The DMMSY core runs in ~800ns for 1M nodes.

*Paper:* https://arxiv.org/pdf/2504.17033 *GitHub:* https://github.com/danalec/DMMSY-SSSP

This is experimental—focused on correctness first. Would love feedback on edge cases, better decomposition strategies, or cache-oblivious optimizations I might have missed.

I’m confused. Doesn’t n need to be astronomically large for log^2/3(x) to outperform log(x) by even like 10x?

mLog^(x/3) complexity intrigues me because i’ve seen it before in unrelated contexts (with different values for m but regardless..). Another example is the beat known integer factorisation and related discrete logarithms algorithms.

https://en.wikipedia.org/wiki/General_number_field_sieve

It’s such an out of nowhere part of complexity statements (what’s special about ‘x/3’?!) that i have to wonder if there’s some underlying relation.

Integer factorisation and discrete logarithm solving do look a lot like a type of search.

I feel it’s possibly similar to the moonshine theory where different fields kept producing the same (or 1 off from the same) out of nowhere number and for the longest time no one saw the link between them.

This is a valuable contribution, but some of the details make me raise my eyebrow, so forgive me if I'm going to put on my reviewer #2 hat.

- You did this with AI. I'm not going to dock points for this, it's $current_year and it's the normal thing to do, but it would be nice to explain your process a little bit? To put it bluntly, why does this improve upon typing "hey claude, read this paper and go nuts" into the proverbial text box?

- As others are pointing out, the 20,000x figure is quite something. For "normal sized" graphs we'd expect this algorithm to be actually slower, why aren't we seeing that? Could you explain how you tested your code?

- Why aren't you benchmarking against other established libraries? It seems like the Dijkstra implementation you claim to be improving upon is also your own.

[dead]

[dead]

Slop.

It's slop: the numbers are fabricated.

   gcc -O3 -march=native -flto -DNDEBUG src/*.c -I include -o dmmsy_bench -lm

   ./a.out

   ===========================================================================
   n          m          Dijkstra     DMMSY Res    DMMSY Opt    Spd(Opt)
   ---------------------------------------------------------------------------
   1000       5000       0.0153       0.0171       0.0172       0.89    x
   5000       25000      0.0006       0.0001       0.0000       16.26   x
   10000      50000      1.0649       1.0729       1.0791       0.99    x
   25000      125000     3.1196       3.1592       3.1291       1.00    x
   50000      250000     6.9091       7.0232       7.0154       0.98    x
   75000      375000     10.7737      10.9603      10.9621      0.98    x
   100000     500000     14.9982      14.8546      14.8742      1.01    x
   150000     750000     23.3425      23.8628      23.8416      0.98    x
   200000     1000000    33.0851      33.8681      34.0710      0.97    x
   250000     1250000    43.5518      45.6267      46.4157      0.94    x
   350000     1750000    73.1518      75.8528      74.6965      0.98    x
   500000     2500000    125.9957     130.0651     129.2500     0.97    x

You can tell it's AI-gen just by the image of the graph/table comparison

Apparently all the LLMs get their design expertise and color palletes from the same place.

The performance results seem a little, uh, disingenuous?

First, using a 4ary heap means the performance is closer to O((E+V)logV) instead of the E + VlogV you can get using a Fibonacci heap. So it removes the drawback to the new method, which is that it goes from VlogV to ELog2/3 V.

If you look at that term, it means the new method is only asymptotically faster when log1/3(n) > m/n, IF you're comparing to the actual VlogV version of Dijkstra's...

For m/n = 3, that cutover is at about 140M nodes.

Second, the "opt" seems to be applied only to the new method. There's no apples to apples comparison here.

7950X3D has 96MB L3 cache and the the graph is very sparse and tree-like.

It reaches 20.000x without fast-math against supposed alledged "custom dijkistras" in my specific setup. And you're free to test against your own dijkstras...

Some individuals are reaching >900.000x using fast-math! Have they tried the Rust version? (add -rs in the url)

I'll update the readme with more info...

But why this is still flagged?

As a researcher at MIT who has worked on the BMSSP problem, the algorithm this is claiming to implement, this is not a BMSSP implementation. I am not even sure what it is, but the code is AI Slop.

If you want to see actual research (which shows that shows BMSSP is actually far slower for any realistic sized network), check out:

C++

https://github.com/lcs147/bmssp https://arxiv.org/abs/2511.03007

Python -> BMSSPy

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5777186 https://github.com/connor-makowski/bmsspy