This algorithm achieves a randomized running time of O(m n^{3/4} + m^{4/5} n) for shortest paths, indicating enhanced efficiency in graph processing.
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 Õ(m n8/9) randomized time. The running time was subsequently improved to Õ(mn4/5) [HJQ25]. We build on [Fin24; HJQ25] to obtain an Õ(m n3/4 + m4/5 n) randomized running time. (Equivalently, Õ(mn3/4) for m ≥ n5/4, and Õ(m4/5 n) for m ≤ n5/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.
No takes yet. Share an insight, caveat, or question.
Huang et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: