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.

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 [11] takes Õ(mn8/9) randomized time. We present an Õ(mn4/5) randomized time algorithm building on ideas from [11].