HackerPapers

arXiv:2602.07868cs.DS

A Faster Directed Single-Source Shortest Path Algorithm

Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Feb 2026 to Feb 2026. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.