# Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Preprint · Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin

- Archive id: arxiv:2504.17033
- Published: 2025-04-23
- arXiv: https://arxiv.org/abs/2504.17033
- Citations: 1
- Source URL: https://arxiv.org/abs/2504.17033
- PDF: https://arxiv.org/pdf/2504.17033
- Provenance: arxiv

## Abstract

We give a deterministic $O(m\\log^{2/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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.