在图 $G = (V, E)$ 中，节点数为 $n = |V|$，边数为 $m = |E|$。$t$-对最短路径问题由 Cohen 提出，旨在近似计算 $t$ 对预先指定的顶点之间的距离。最近，特别是在 $t = \Theta(n)$ 的情况下，$n$-对最短路径问题受到新的关注。Dalirrooyfard, Jin, Vassilevska Williams 和 Wein 以及 Chechik, Hoch 和 Lifshitz 提出了新算法和条件下界。
本文首次为加权无向图中的 $n$-对最短路径问题提出了一种 $(2 - \alpha)k$-近似算法，其中常数 $\alpha > 0$，运行时间为 $\tilde{O}(mn^{1/k} + n^{1 + 2/k})$。具体来说，我们提出了一个 $1.622k$-近似算法，改进了 Chechik, Hoch 和 Lifshitz 提出的 $(2k - 3)$-近似算法，适用于非超稀疏图，从而回应了他们提出的开放问题。此外，我们还开发了更好的近似算法，针对无权图和稠密加权图，超越了 Dalirrooyfard 等人以及 Chechik, Hoch 和 Lifshitz 的结果。
我们主要的技术贡献是新的重边技术。通过该技术，我们将一个近似保证依赖于 $W_{uv}$（即 $u$ 和 $v$ 之间最短路径上最重边的权重）的算法转变为一个完全乘法近似的算法，该算法不依赖于 $W_{uv}$。
博主点评： 这篇论文在加权无向图的 $n$-对最短路径问题上取得了显著的进展，尤其是通过重边技术的引入，提升了算法的性能。这种新思路为图算法的研究提供了新的视角，值得进一步探索其在其他图算法中的潜在应用。