Hugging Face's logo
Papers
arxiv:2504.17033

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Published on Apr 23, 2025
Upvote
-
Authors:
,
,
,
,

Abstract

We give a deterministic O(mlog^{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+nlog n) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

View arXiv page View PDF Add to collection

Community

grantsing

arXiv explained breakdown of this paper 👉 https://arxivexplained.com/papers/breaking-the-sorting-barrier-for-directed-single-source-shortest-paths

Sign up or log in to comment

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2504.17033 in a model README.md to link it from this page.

Datasets citing this paper 0

No dataset linking this paper

Cite arxiv.org/abs/2504.17033 in a dataset README.md to link it from this page.

Spaces citing this paper 0

No Space linking this paper

Cite arxiv.org/abs/2504.17033 in a Space README.md to link it from this page.

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.