最后，负图上最短路径的快速算法

在算法中，就像在生活中一样，消极情绪可能是一种拖累。

考虑寻找图上两点之间的最短路径的问题——由链接或边连接的节点网络。通常，这些边是不可互换的：一张图可以表示一张路线图，其中一些道路比其他道路慢或收费更高。计算机科学家通过将每条边与一个“权重”配对来解释这些差异，该“权重”可以量化跨越该部分的成本——无论该成本代表时间、金钱还是其他东西。自 1950 年代以来，他们已经知道如何在理论上尽可能快地找到最短路径，假设所有权重都是正数。

但是在某些图上权重可能是负的——沿着一个线段行进可以抵消穿过另一条线段的成本。例如，考虑一个送货司机，他必须平衡汽油和通行费成本（以正权重表示）与运输包裹的收入（以负权重表示）。在这种情况下，最快的已知最短路径算法不起作用。几十年来，在负权重图上寻找最短路径的快速算法仍然难以捉摸。

但是负权重会给 Dijkstra 的贪婪策略带来麻烦。再想想我们的送货司机。从 A 到 B 的直接路线赚取的利润很少，可能比在某处有大回报的迂回路线赚的钱少。 “你不能仅根据本地信息做出决定，”宾夕法尼亚大学的计算机科学家Sanjeev Khanna说。 “你可能不得不做出几个看似次优的举动才能最终获得真正的回报。”

几十年来，研究负权重图的计算机科学家试图将 Dijkstra 算法的速度与类似的“组合”算法相匹配。这些涉及离散操作——如计算可能性、修改权重和有选择地删除边——反映了底层图的离散结构。然而，到 1990 年代进展放缓。最近，研究人员使用了“持续优化”算法，它借鉴了微积分的技巧。不幸的是，由此产生的加速是有限的，而且往往以简化为代价。

打破循环

2021 年夏天，成为哥本哈根大学同事的两位计算机科学家Danupon Nanongkai和Christian Wulff-Nilsen正在为一个联合研究项目寻找主题。 “Christian 说，’哦，顺便说一句，我正在度假，正因为如此，我正试图想出一些非常雄心勃勃的事情，’”Nanongkai 回忆道，他现在在德国萨尔布吕肯的马克斯普朗克信息学研究所工作。他们解决了负权重最短路径问题，并邀请罗格斯大学的Aaron Bernstein加入他们的行列。

Christian Wulff-Nilsen 正在寻找一个雄心勃勃的问题来与他的合作者一起解决。他们决定寻找一种快速算法，可以在负权重的图中找到最短路径。

这三位研究人员都是解决其他问题的组合图算法方面的专家，他们想看看这些相对古老的方法能走多远。 “实际上，在解决一个雄心勃勃且开放了很长时间的问题时有一定的自由度，”伯恩斯坦说。

三人组首先暂时忽略了可能图形的一个子集：那些包含负循环的图形。这些路径在经过一系列权重加起来为负数的边后循环回到它们开始的地方。在从起点可到达负循环的图中，最短路径的概念被打破，因为您可以通过在负循环之前重复几圈，使到任何节点的距离为负（或有利可图）前往目的地。

研究人员怀疑，较长的负路径是导致问题变得困难的主要原因。所以他们开始关注附近节点的紧密集群，这些节点不能包含任何长的负路径：这是因为如果两点通过一条短的正路径连接，在它们之间添加一条长的负路径会产生一个负循环。在一个紧密的集群中，“事实上每个人在积极意义上都靠得很近，实际上也为你提供了有关消极边缘的有用信息，”伯恩斯坦说。 “它告诉你事情不能太消极。”

大多数图都包含许多这样紧密的簇，它们彼此之间的联系很弱。如果研究人员能够查明所有集群，他们怀疑他们可以开发出一种方法来快速找到每个集群中的最短路径。从那里，他们可能会更轻松地连接各个集群并在原始图形上找到最短路径。但这需要快速找出节点靠在一起的任何图形区域——这是他们不知道该怎么做的。结果证明，关键是一种起源于图论完全不同分支的技术。

切割图

在 20 世纪 80 年代，计算机科学家开发了一种称为低直径分解的技术来挑选图中的紧密簇并确定要删除的边以分离这些簇。这种技术提供了一种将图形划分为独立部分的方法。它是为了促进“分布式”算法而发明的，在这种算法中，计算在图形的不同部分并行运行，因此它对于不具有此属性的最短路径算法的用处不大。

Danupon Nanongkai 帮助开发了新算法，该算法通过关注没有太多负面影响的部分来找到图中的最短路径。

Bernstein、Nanongkai 和 Wulff-Nilsen 意识到小直径分解可以帮助他们识别没有太多集中负性的星团。不幸的是，标准的低直径分解算法仅适用于无向图——其中每条边都可以在两个方向上遍历的图。同时，负权重最短路径问题仅在有向图上有意义，其中每条边都是单向街道。 （否则，一个单一的无向负边会产生一个负循环，由在该边上来回重复跳跃组成。）如果研究人员想使用低直径分解，他们必须对其进行调整。

这就是他们在新论文中所做的。受 Bernstein 和 Wulff-Nilsen 过去与 Probst Gutenberg 合作的工作的启发，他们开发了一种类似于低直径分解的有向图的破碎程序。该过程通过使用随机过程删除少量边，将任意有向图分割成一系列紧密结合的簇。之后，这些集群由一个稀疏网络连接，其中所有边都指向同一方向。这种网络称为有向无环图或 DAG。

将 DAG 想象成一条溪流，其中的水可能沿着不同的路径流动：一些路径从不同的源头流入，另一些则向不同的方向散开，还有一些可能分开并重新合并在一起。但是没有任何东西会倒流，所以没有循环；这使得 DAG 更容易使用。

研究人员早就知道如何在 DAG 上快速找到最短路径，即使权重为负。因此，压裂技术使三位研究人员能够将任何有向图简化为两种特殊情况的组合——DAG 和紧密集群——这两种情况都很容易处理。

新的最短路径算法反复使用分裂过程将图形分解为由 DAG 连接的紧密集群。然后它将这些集群越来越远地分开。在此过程结束时，最内层的集群将尽可能紧密地连接在一起。该算法速度如此之快的部分原因在于，即使是一个非常大的图，也不需要多次迭代就可以完全分解，就像如果你反复除法，不需要很长时间就可以将一个大数减少到合理的大小一样它减半。

通过以这种方式完全分解图表，研究人员可以快速找到通过图表每个部分的最短路径。对于嵌套图结构最内层的紧密簇，这很容易——它们几乎没有负值。研究人员已经知道如何在连接它们的 DAG 部分上找到最短路径。

最后，该算法将分割过程中消除的边加回去，并计算它们对最短路径的影响。研究人员证明，他们随机删除边的过程几乎总是只需要删除几条就可以消除“向后”边——这种边可以将他们的 DAG 变成具有大循环的图。这使得任何最短路径极不可能通过太多这样的向后段，因此他们可以通过结合 1950 年代的两种教科书方法来解决这个棘手的最后一步：Dijkstra 算法和第一个为负权重图开发的算法。

Aaron Bernstein 曾与 Wulff-Nilsen 合作解决过一个涉及切割图形的问题。他们意识到类似的方法可能适用于负权重最短路径问题。

“这是对这些想法的极其巧妙的组合，”卡纳说。该算法是第一个以“近线性”时间运行的负权重图——这意味着它的运行时间几乎与计算所有边所需的时间成正比，它可能是最快的。

那些研究人员一开始决定忽略的负循环图呢？在完成最短路径算法的最后润色后，他们表明它也可以作为一种快速算法来精确定位负循环。几乎没有图表超出它的范围。

并行路径

伯恩斯坦在 2022 年计算机科学基础会议上展示了该团队的成果，他们描述新算法的手稿被认为是两篇最佳论文之一。另一篇论文也碰巧描述了一种新的近线性时间算法，用于解决图论中一个长期存在的问题。

该算法由 Probst Gutenberg 和其他五位研究人员开发，解决了一个更普遍的问题，称为最小成本流，其目标是优化通过多条并行路径的传输，并且每条边都有最大容量和相关成本.最短路径问题是最小成本流的特例，因此新的最小成本流算法也可用于在近线性时间内解决负权重最短路径问题，尽管采用的方法完全不同。

致力于最小成本流程的团队使用组合和连续优化技术的复杂综合开发了他们的通用快速算法，这使得它在实践中难以使用，至少目前是这样。 Bernstein 及其同事的组合算法虽然仅限于更具体的问题，但在不牺牲简单性的情况下实现了接近线性的运行时间。

“这就是这篇论文的惊人之处，”Probst Gutenberg 说。 “你可以给本科生解释，也可以在你的电脑上实现。”

因此，这种新算法重新引起了人们对图论中其他问题的组合方法的兴趣。哪些问题可以使用纯组合算法快速解决，哪些问题确实需要过去 20 年开发的连续技术，还有待观察。

“这是一个我试图去理解的哲学问题，”纳农凯说。 “这个最短路径问题带来了一些希望。”