研究人员提出了一种新方法，能够更快地解决计算机科学中的经典问题——寻找网络中最短路径。传统方法需要反复排序以确定最近点，但新方法通过优化排序过程，显著提高了算法效率，使其成为目前最快的路径搜索解决方案。这一突破对实际生活中的路径规划具有重要意义。

新方法：寻找最佳路径的最快方式

在解决复杂问题时，通常需要有条理地进行。例如，将问题分解为多个部分，并先处理最简单的部分。然而，这种排序过程本身会消耗时间，可能导致效率低下。这一困境在计算机科学中尤为突出，尤其是在寻找网络中从起点到其他所有点的最短路径问题上。这个问题类似于我们在日常生活中寻找从新家到工作地点、健身房和超市的最佳路线。

哥本哈根大学的计算机科学家Mikkel Thorup表示：“最短路径问题是一个全球任何人都能理解的美妙问题。”

直觉上，找到到附近目的地的最短路径应该是最容易的。因此，设计一个最快的最短路径算法似乎应该从找到最近的点开始，然后是次近的点，依此类推。然而，这种方法需要反复确定哪个点最近，即按距离排序。任何遵循这种方法的算法都有一个基本的速度限制：不能比排序所需的时间更快。

四十年前，研究人员在设计最短路径算法时遇到了这个“排序障碍”。如今，一个研究团队开发了一种新的算法，打破了这一障碍。该算法不进行排序，并且比任何排序算法运行得更快。

普林斯顿大学的计算机科学家Robert Tarjan表示：“作者们大胆地认为他们可以打破这一障碍，这是一个惊人的结果。”

知识前沿

为了从数学上分析最短路径问题，研究人员使用图论的语言——由点和线组成的网络。每个节点之间的连线都有一个称为权重的数字，可以表示该段的长度或通过它所需的时间。通常，任意两个节点之间有许多路径，最短路径是权重总和最小的路径。给定一个图和特定的“源”节点，算法的目标是找到到其他所有节点的最短路径。

1956年，计算机科学家Edsger Dijkstra设计的最短路径算法从源节点开始，逐步向外扩展。这种方法之所以有效，是因为知道到附近节点的最短路径有助于找到到更远节点的最短路径。但由于最终结果是一个按最短路径排序的列表，排序障碍设定了算法运行速度的基本限制。

1984年，Tarjan和另一位研究人员改进了Dijkstra的原始算法，使其达到了这一速度限制。任何进一步的改进都必须来自避免排序的算法。

在20世纪90年代末和21世纪初，Thorup和其他研究人员设计了一些打破排序障碍的算法，但这些算法需要对权重做出某些假设。没有人知道如何将这些技术扩展到任意权重。似乎他们已经走到了尽头。

清华大学计算机科学家Ran Duan表示：“研究停滞了很长时间，许多人认为没有更好的方法。”

Duan并不这么认为。他长期以来一直梦想构建一个可以在所有图上打破排序障碍的最短路径算法。去年秋天，他终于成功了。

突破排序

Duan对排序障碍的兴趣可以追溯到近20年前他在密歇根大学研究生时期，当时他的导师是研究如何在特定情况下打破排序障碍的研究人员之一。但直到2021年，Duan才设计出一个更有前景的方法。

关键在于关注算法在每一步中下一步的去向。Dijkstra的算法会考虑在先前步骤中已经探索过的区域，并通过扫描该区域的“边界”来决定下一步的去向。这种方法在开始时不需要太多时间，但随着算法的进展会变得越来越慢。

Duan设想将边界上的相邻节点分组为簇，然后只考虑每个簇中的一个节点。由于需要筛选的节点更少，每一步的搜索速度可以更快。算法最终可能会选择去往非最近节点，因此排序障碍不再适用。但确保这种基于簇的方法实际上使算法更快而不是更慢将是一个挑战。

Duan在接下来的一年中充实了这一基本想法，到2022年秋天，他对克服技术障碍感到乐观。他邀请了三位研究生帮助解决细节问题，几个月后，他们提出了一个部分解决方案——一个打破排序障碍的算法，但仅适用于所谓的无向图。

在无向图中，每条链接都可以双向通过。计算机科学家通常对包含单向路径的更广泛的图类更感兴趣，但这些“有向”图通常更难导航。

斯坦福大学计算机科学研究生Xiao Mao表示：“可能存在A可以很容易到达B，但B不能很容易到达A的情况，这会带来很多麻烦。”

有前景的路径

2023年夏天，Mao在加利福尼亚的一次会议上听到Duan关于无向图算法的演讲。他与Duan进行了交谈，他长期以来一直钦佩Duan的工作。

Mao回忆道：“我第一次在现实生活中见到他，非常兴奋。”

会议结束后，Mao开始利用业余时间思考这个问题。与此同时，Duan和他的同事们正在探索适用于有向图的新方法。他们从另一个著名的最短路径算法——Bellman-Ford算法中汲取灵感，该算法不生成排序列表。乍一看，这似乎是一个不明智的策略，因为Bellman-Ford算法比Dijkstra的算法慢得多。

Thorup表示：“每当进行研究时，你都会尝试走一条有前景的道路。我几乎会认为选择Bellman-Ford是反有前景的，因为它看起来完全像是你能做的最愚蠢的事情。”

Duan的团队通过每次只运行Bellman-Ford算法的几个步骤来避免其缓慢性。这种选择性使用Bellman-Ford使他们的算法能够提前侦察出在后续步骤中最有价值的节点。这些节点就像道路网络中的主要交叉路口。

Thorup说：“你必须通过它们才能获得到许多其他东西的最短路径。”

2024年3月，Mao想到了另一个有前景的方法。团队原始方法中的一些关键步骤使用了随机性。随机算法可以高效地解决许多问题，但研究人员仍然更喜欢非随机方法。Mao设计了一种无需随机性解决最短路径问题的新方法。他加入了团队，他们在接下来的几个月里通过群聊和视频通话合作，将他们的想法合并。最终，在秋天，Duan意识到他们可以借鉴他在2018年设计的一个算法中的技术，该算法打破了另一个图问题的排序障碍。这一技术是他们需要的最后一块拼图，用于一个在无向图和有向图上都比Dijkstra算法运行得更快的算法。

完成的算法将图分层，像Dijkstra算法一样从源节点向外移动。但它不是每一步都处理整个边界，而是使用Bellman-Ford算法精确定位有影响力的节点，从这些节点向前移动以找到到其他节点的最短路径，然后再回到其他边界节点。它并不总是按距离递增的顺序找到每一层中的节点，因此排序障碍不适用。如果你以正确的方式分割图，它的运行速度比Dijkstra算法的最佳版本略快。它更为复杂，依赖于许多需要完美配合的部分。但奇怪的是，没有任何部分使用复杂的数学。

Thorup说：“这个东西可能在50年前就被发现了，但事实并非如此。这使它更加令人印象深刻。”

Duan和他的团队计划探索是否可以简化算法以使其更快。随着排序障碍的消失，新算法的运行时间并不接近计算机科学家已知的任何基本限制。

Tarjan说：“作为一个乐观主义者，我不会感到惊讶，如果你能进一步降低它。我当然不认为这是过程的最后一步。”

评论内容主要围绕Tarjan的算法贡献、新算法的复杂性及其与Dijkstra算法的比较展开。以下是总结：

1. Tarjan的贡献

   • 评论1提到Tarjan是算法领域的教授，发明了许多算法。
     引用：
     "Tarjan was my algorithms professor. He invented many of them."
     （Tarjan是我的算法教授，他发明了许多算法。）

2. 新算法的简洁性与创新性

   • 评论2指出新算法并未使用复杂的数学，但其发现令人印象深刻，甚至可能被游戏开发者偶然发现。
     引用：
     "This thing might as well have been discovered 50 years ago, but it wasn’t. That makes it that much more impressive."
     （这个东西本可以在50年前被发现，但并没有，这使它更加令人印象深刻。）
     "it feel like a solution you could have stumbled upon while doing game development or something."
     （它感觉像是你在游戏开发中可能偶然发现的解决方案。）

3. 与Dijkstra算法的比较

   • 评论3认为新算法比Dijkstra更复杂，但这是算法发展的趋势。
     引用：
     "Sounds a lot more complicated that Dijkstra. But I guess that's the way it goes."
     （听起来比Dijkstra复杂得多，但我想这就是趋势。）
   • 评论5对新算法的“全局最小值”保证表示好奇，担心其可能遗漏某些解。
     引用：
     "Im most curiosity how the algorithm fulfil the 'global minima' that djixtra guarantees."
     （我最好奇的是这个算法如何实现Dijkstra保证的“全局最小值”。）

4. 算法的复杂性分析

   • 评论4对新算法的时间复杂度表示赞叹。
     引用：
     "O(m log^2/3 n) !!! What a triumph."
     （O(m log^2/3 n)！！！多么伟大的成就。）
   • 评论6指出新算法在密集图中的表现可能不如Dijkstra，并讨论了排序障碍的适用性。
     引用：
     "First, note that this complexity is actually worse for highly dense graphs."
     （首先，请注意这个复杂度在高度密集的图中实际上更差。）
     "Also note that the 'sorting barrier' only applies to comparison-based sorts."
     （还要注意，“排序障碍”仅适用于基于比较的排序。）

5. 算法的潜在改进

   • 评论7提出通过引入随机性来探索边界，可能进一步加速算法。
     引用：
     "I wonder if hybridizing this with selective use of randomness to probe beyond frontiers leads to another speedup."
     （我想知道，如果将其与选择性使用随机性结合起来，探索边界是否会导致另一种加速。）

总结：评论中对Tarjan的贡献表示认可，新算法的简洁性和创新性受到赞赏，但其复杂性和在密集图中的表现引发讨论。与Dijkstra算法的比较中，新算法的“全局最小值”保证和潜在改进方向成为关注点。