Faster negative length shortest paths by bootstrapping hop reducers
Y. P. Huang, Peter Jin, Kent Quanrud · Society for Industrial and Applied Mathematics eBooks · 2026
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 takes \(\tilde{O}(mn^{8/9})\) randomized time. The running time was subsequently improved to \(\tilde{O}(mn^{4/5})\) by Huang, Jin, and Quanrud.