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

**Authors:** Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin  
**arXiv:** [2504.17033](https://arxiv.org/abs/2504.17033)  
**Date:** 2025-04-23  
**Summary page:** https://www.summarizepaper.com/fr/paper/2504.17033v2/

## 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.