
























The textbook algorithm for real-weighted single-source shortest paths takes $O(m n)$ time on a graph with $m$ edges and $n$ vertices. The breakthrough algorithm by Fineman [Fin24] takes $\tilde{O}(m n^{8/9})$ randomized time. The running time was subsequently improved to $\tilde{O}(mn^{4/5})$ [HJQ25]. We build on [Fin24; HJQ25] to obtain an $\tilde{O}(m n^{3/4} + m^{4/5} n)$ randomized running time. (Equivalently, $\tilde{O}(mn^{3/4})$ for $m \geq n^{5/4}$, and $\tilde{O}(m^{4/5} n)$ for $m \leq n^{5/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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。