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.
Here’s the scientific article: https://arxiv.org/pdf/2504.17033
The abstract (emphasis mine):
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.