What type of study is this?

This is a Quantitative Study study.

synapse

⌘+K

synapse

⌘+K

October 19, 2025Open Access

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Key Points

The proposed algorithm achieves a time complexity of O(m log^{2/3} n), breaking previous bounds.
This result indicates Dijkstra's algorithm is not optimal for single-source shortest paths on sparse graphs.
The method operates under the comparison-addition model, showcasing improvements in algorithm efficiency.
This work contributes to graph theory by providing a new perspective on solving shortest path problems.

Abstract

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

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper

Cite This Study

Duan et al. (Wed,) studied this question.

synapsesocial.com/papers/68f43f09854d1061a58aca51 https://doi.org/https://doi.org/10.48550/arxiv.2504.17033

Mark Helpful

Bookmark

Relay

View Full Paper