Faster negative length shortest paths by bootstrapping hop reducers

Yufan Huang, Peter Jin, Kent Quanrud

The textbook algorithm for real-weighted single-source shortest paths takes $O(mn)$ time on a graph with $m$ edges and $n$ vertices. The breakthrough algorithm by Fineman [Fin24]…