大多数人都用过类似谷歌地图的导航应用，这类应用依赖于在庞大网络中寻找最短路径的算法。现在，把这个任务从“起点到终点”扩展为“系统中任意两点之间”的距离计算，例如在交通网络、通信骨干网，甚至蛋白质相互作用或神经连接等生物网络中，这就变成了一个更为基础而困难的问题。

这正是经典的“所有点对最短路径”（All-Pairs Shortest Paths，APSP）问题，它是理论计算机科学中的核心课题之一。APSP要求在一个图中，计算每一对顶点之间的最短路径距离。这里的“图”是由顶点和边构成的网络：顶点可以代表城市、计算机、地铁站或人体器官，边则对应道路、电缆、轨道或血管等连接。

在大型图上精确计算所有顶点对的距离，时间和空间开销都非常高。对于稠密网络，运行时间通常是立方级的：如果网络规模翻一倍，计算量大约会增加到原来的八倍，增长速度远超网络本身的扩张。因此，几十年来，研究者一直在寻找更快的近似算法——在显著降低运行时间的前提下，给出与真实距离非常接近的估计值。

经典“捷径”算法的思路

早在1996年，Dor、Halperin和Zwick（简称 DHZ）证明，可以在近乎最优的时间内得到不超过真实距离两倍的估计，即所谓“2-近似”。直观地说，如果真实距离是 10 公里，他们的方法保证输出在 10 到 20 公里之间。

为了实现这一点，DHZ算法在网络中随机选取一小部分顶点作为“采样顶点”。在估计两个顶点之间的距离时，算法不再穷举所有可能路径，而是借助这些采样顶点来快速推断距离。

如果要估计德里到钦奈这样长距离的行程，DHZ的捷径通常既快又相当可靠。对于相距较远的顶点对，采样顶点往往落在它们之间的某条最短路径附近，因此估计值通常不会超过真实最短路径的两倍。

但在短距离场景下，例如孟买郊区两个相邻社区之间的距离，这种捷径就可能出现较大误差。关键问题在于：对于距离较近的顶点对，算法并不能始终保证估计值不超过真实值的两倍。比如，真实最短路径只需要两条边，但通过采样顶点得到的估计可能是五条边（已经超过两倍），从而违背了“最多两倍”的理论保证。对于本来就很近的顶点，这种“绕远路”会显著扭曲结果。

这一局限在近25年里一直没有被突破。

多尺度细化：新的算法框架

在第66届计算机科学基础年会（FOCS 2025）上，印度理工学院甘地讷格尔分校副教授 Manoj Gupta 博士提出了一种针对大规模网络中“距离较近顶点对”的显著改进方法。他在论文《针对距离较近顶点对的改进2-近似最短路径》中系统介绍了这一新思路。

Gupta 博士展示了如何在不增加整体运行时间的前提下，为比以往认为可能范围更近的顶点对，高效计算其2-近似距离。

传统方法主要依靠在图中选取一层“代表性”采样顶点来估计距离。而新方法在此基础上引入了多尺度的采样细化：

• 不再只使用单一层次的采样顶点；
• 而是在多个尺度上组织和分层这些采样点；
• 通过分层整合图结构信息，更精细地捕捉短路径结构。

这种多尺度设计，使算法在保持原有时间复杂度不变的情况下，显著降低了“2-近似保证”所要求的最小距离阈值。换言之，2-近似不再只对“足够远”的顶点对有效，而是扩展到了更短的距离范围。其核心进步就在于更精巧的采样策略和分层组织方式。

简要对比可以概括为：

• DHZ算法：在效率上表现优异，但理论保证主要适用于较长距离；
• 新算法：在不牺牲甚至可能提升速度的同时，将“有保证的2-近似”扩展到更短的距离区间（例如类似孟买郊区内部的短途场景）。

这一边界的推进，正是该工作的关键贡献所在。

理论突破的现实意义

这一进展为何重要？因为大型网络已经渗透到各类关键系统：从互联网路由、城市交通，到社交网络以及依赖图数据的人工智能系统。在实际应用中，人们往往更关心“足够快、足够大规模、误差可控”的近似结果，而不是每一条路径的绝对精确值。

新算法正是面向这种需求：在大规模图上，以近乎最优的时间给出高质量的近似距离估计，尤其在短距离范围内提供了此前难以获得的理论保证。

改进一个长期存在的理论界限，并不仅仅是纸面上的胜利。它帮助我们更好地理解：局部连接模式如何塑造整个网络的全局结构，也让我们在“快速近似计算所有点对距离”的目标上更进一步。

在这个进展通常极为缓慢的研究方向上，能在1996年结果的基础上取得实质性改进，是一次重要的跨越。缩小这块长期存在的空白，强化了可扩展图算法的理论根基——而这些算法，正是支撑众多复杂互联系统平稳运行的隐形引擎。