Improved Approximation Algorithms for n-Pairs Shortest Paths
2026-07-02 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where you want to quickly estimate the shortest distances between many specific pairs of points in a weighted network. They improve previous algorithms by finding a new method that gives a better approximation (closer to the true distance) and runs efficiently for graphs that aren't extremely sparse. Their main innovation is a technique called "heavy-edge," which helps remove dependence on the heaviest edge weight on a path, making the approximation purely multiplicative. They also provide better algorithms for both unweighted and dense weighted graphs, answering some open questions from prior work.
graphweighted graphshortest pathsapproximation algorithmsn-Pairs Shortest Pathsmultiplicative approximationalgorithm complexityheavy-edge techniquedense graphunweighted graph
Authors
Avi Kadria, Liam Roditty, Virginia Vassilevska Williams
Abstract
Let $G = (V, E)$ be a graph with $n = |V|$ nodes and $m = |E|$ edges. The $t$-Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distances between $t$ prespecified pairs of vertices. Recently, this problem has received renewed attention, particularly in the case where $t = Θ(n)$: the $n$-Pairs Shortest Paths problem. In this setting, new algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein [FOCS'22], and Chechik, Hoch, and Lifshitz [SODA'25]. In this paper, we present the first algorithm for the $n$-Pairs Shortest Paths problem in \textit{weighted} undirected graphs that achieves a $(2 - α)k$-approximation, for constant $α> 0$, that runs in $\tilde{O}(mn^{1/k} + n^{1 + 2/k})$ time. Specifically, we present a $1.622k$-approximation, improving upon the $(2k - 3)$-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for graphs that are not super sparse, which answers in the affirmative the open question posed by them. We also develop improved approximation algorithms with better tradeoffs for unweighted graphs and dense weighted graphs that improve upon the results of Dalirrooyfard \etal~and Chechik, Hoch, and Lifshitz. Our main technical contribution is the new \textit{heavy-edge} technique. Using this technique, we transform an algorithm with an approximation guarantee that depends on $W_{uv}$, the weight of the heaviest edge on the shortest path between $u$ and $v$, into an algorithm with purely multiplicative approximation that does not depend on $W_{uv}$.