mlsanityData to 14 Oct 2026

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

arXiv 2504.17033 ↗First posted 23 Apr 2025cs.DScited by 1

Not on the map. Why?

Abstract (arXiv)

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+nlog n) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 23 Apr 2025.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Physical Transformercited by 0