Faster negative length shortest paths by bootstrapping hop reducers

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] takes $\tilde{O}(m{n}^{8\mathrm{/}9})$ randomized time. The running time was subsequently improved to $\tilde{O}(m{n}^{4\mathrm{/}5})$ [HJQ25]. We build on [Fin24; HJQ25] to obtain an $\tilde{O}(m{n}^{3\mathrm{/}4}+m^{4\mathrm{/}5}n)$ randomized running time. (Equivalently, $\tilde{O}(m{n}^{3\mathrm{/}4})$ for $m\ge n^{5\mathrm{/}4}$, and $\tilde{O}(m^{4\mathrm{/}5}n)$ for $m\le n^{5\mathrm{/}4}$.) The main new technique replaces the hop-reducing auxiliary graph from [Fin24] with a bootstrapping process where constant-hop reducers for small subgraphs of the input graph are iteratively amplified and expanded until the desired polynomial-hop reduction is achieved over the entire graph.