this post was submitted on 03 Oct 2025
11 points (92.3% liked)

Hacker News

2751 readers
669 users here now

Posts from the RSS Feed of HackerNews.

The feed sometimes contains ads and posts that have been removed by the mod team at HN.

founded 1 year ago
MODERATORS
patrick@lemmy.bestiver.se
rssbot@lemmy.bestiver.se
11
Move over Dijkstra: New Algorithm Just Rewrote 70 Years of Computer Science (medium.com)
submitted 5 days ago by rssbot@lemmy.bestiver.se to c/hackernews@lemmy.bestiver.se
2 comments fedilink hide all child comments
 

Comments

you are viewing a single comment's thread
view the rest of the comments
[–] 0ops@piefed.zip 5 points 5 days ago

Here's the scientific article: https://arxiv.org/pdf/2504.17033

The abstract (emphasis mine):

We give a deterministic O(m log2/3 n)-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 + n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP

So this article's a bit clickbaity in that this algorithm only outperforms Dijkstra's in those specific cases, which aren't uncommon, but Dijkstra's is still king for undirected graphs, or graphs with negative edge weights. Still very neat.