Faster single-source shortest paths with negative real weights via proper hop distance

Yufan Huang; Peter Jin; Kent Quanrud

doi:10.1137/1.9781611978322.178

SODA2025Top-tier venue

Faster single-source shortest paths with negative real weights via proper hop distance

Yufan Huang, Peter Jin, Kent Quanrud

arXiv DOI Publisher

2025Year

5Citations

8Top-tier citations

Abstract

The textbook algorithm for single-source shortest paths with real-valued edge weights runs in O(mn) time on a graph with m edges and n vertices. A recent breakthrough algorithm by Fineman [Fin24] takes Õ mn 8/9 randomized time. We present an Õ mn 4/5 randomized time algorithm building on ideas from [Fin24].