这一挑战远不止于地图。类似的计算对于交通系统、通信网络，甚至涉及蛋白质、神经元或其他相互连接组件的生物结构都非常重要。随着这些网络的不断增长，确定所有点之间的最短路径变得越来越困难。
计算机科学家将此称为所有点对最短路径（All-Pairs Shortest Paths，APSP）问题。它涉及寻找图中每一对点之间的最短距离。在这里，“图”只是由点（称为顶点）和连接（称为边）组成的集合。这些点可以代表城市、个人电脑、地铁站或器官，而连接可以代表高速公路、电缆、铁路线路或血管。
为什么计算最短路径如此困难
在庞大的网络中确定精确的最短距离会消耗大量的计算时间和内存。在连接密集的网络中，一些传统方法需要数学家所说的立方时间。这意味着点数翻倍会使计算工作量增加约八倍。
由于所需的计算（工作量）增长速度可能远超网络本身的增长速度，研究人员花费数十年寻找更高效的方法。一种有前景的解决方案是使用近似算法，即计算估计值而非精确答案。其目标是在大幅减少所需计算量的同时，产生足够准确的距离。
一个重要进展出现在1996年，研究人员Dor、Halperin和Zwick（DHZ）开发了一种方法，能够在接近最优的时间内，为距离足够远的点产生在实际最短距离两倍以内的距离估计值。
这种精度水平被称为“2近似”。例如，如果两个地点之间可能的最短路线是10公里，那么满足这一保证的估计值将落在10到20公里之间。
DHZ方法并非检查每一条可能的路线，而是使用网络中相对较少的一部分点（称为采样顶点）。这些经过战略性选择的点充当捷径，帮助算法更高效地估计距离。
一个隐藏着弱点的巧妙捷径
当被比较的点相距很远时，该方法效果特别好。
考虑一下德里与金奈之间的旅程。由于这两座城市相距甚远，算法通常能够找到一个靠近最短路线的采样点。这使它能够计算出保持在承诺的实际距离两倍以内的估计值。
然而，当两个点距离很近时，同样的策略就变得不那么可靠了。
想象一下计算孟买郊区两个社区之间的最短路线。采样点可能离最直接的连接太远，迫使算法估计出一条长得多的路线。
例如，两个点可能仅由包含两条边的路径连接，而采样路线却可能包含五条边。由于五超过了真实距离二的两倍，该结果违反了“至多两倍”的精度保证。
这一弱点意味着原始算法的数学保证仅在点相距足够远时才适用。对于较近的连接，并不总能保证同样的精度水平。
这一局限性在近三十年里一直是一个挑战。
新算法突破数十年的限制
如今，印度理工学院甘地纳加尔分校副教授Manoj Gupta博士提出了一种改进方法，将精度保证扩展到了比以往方法所允许的更接近的点。
Gupta在第66届计算机科学基础年度研讨会（FOCS 2025）上展示了他的研究，论文题为"Improved 2-Approximate Shortest Paths for close vertex pairs"（针对近距顶点对的改进型2近似最短路径）。
这一成就尤为重要，因为改进后的算法在保持先前方法整体运行时间的同时，扩大了可保证可靠估计的距离范围。
这一突破源于对网络中点如何采样的重新思考。
传统方法依赖一组代表性点来估计距离。Gupta的方法则引入了一种多尺度采样策略，在若干不同层级上组织网络信息。
通过在多个尺度上分析连接，而不是依赖单一采样层，该算法能够考虑到以前方法可能忽略的较短路线。
这种更精细的采样技术降低了2近似保证成立所需的最小距离，同时没有增加算法的整体计算复杂度。
回到交通的例子，原始的DHZ方法能够高效估计足够长的旅程，例如德里与金奈之间的路线。而改进后的方法将这种可靠的精度扩展到了更短的连接（例如孟买的郊区）。
其核心成就不仅仅是一种估计距离的新方法，而是在保持计算效率的同时，能够在更广泛的距离范围内提供相同数学精度保证的能力。
为什么这一计算机科学突破如此重要
庞大的网络是现代技术的基础。互联网基础设施、交通系统、社交媒体平台和人工智能应用都依赖于对复杂的互联信息网络的分析。
在许多情况下，快速获得可靠的估计比获得完全精确的距离更为重要。当网络包含数量庞大的连接时，平衡准确性与速度的能力就显得尤其有价值。
Gupta的研究强化了用于应对这些挑战的算法的数学基础。尽管这些成果是理论性的，并不能立即改善特定的商业系统，但它们为大型网络中的距离计算提供了一种更好的方法。
这项工作还提供了关于如何通过精心选择的局部连接来理解网络整体结构的洞见。通过改进这些关系的采样和分析方式，研究人员可以更接近于高效估计庞大系统中每一对点之间的距离。
理论计算机科学的进步往往来自渐进式的改进，而非剧变式的变革。因此，改进一项可追溯至1996年的有影响力的成果，代表着一次有意义的进展。
通过在不增加整体运行时间的前提下扩展长期存在的精度保证，这一新算法突破了重要的数学界限，并强化了支撑当今一些最复杂互联系统的技术基础。