首页科技快讯突破四十年“排序障碍”：清华团队提出寻找最短路径新方法

突破四十年“排序障碍”：清华团队提出寻找最短路径新方法

来源：晰数塔互联网快讯时间：2025年10月02日 15:12

本文来自微信公众号：集智俱乐部（ID：swarma_org），作者：Ben Brubaker

导语

在计算机科学的漫长发展历程中，某些经典算法如同基石般屹立数十年，被视为难以逾越的巅峰。其中，Dijkstra算法自1956年问世以来，一直是求解网络中最短路径问题的“黄金标准”。然而，其性能长期受制于一个被称为“排序障碍”的根本性限制——任何依赖逐步排序节点的算法，其速度无法快于排序本身所需的时间。这一瓶颈困扰学界长达四十余年，直至今日，终被打破。清华大学段然团队携手斯坦福大学毛潇等研究者，提出了一种革命性新算法：它摒弃了传统的排序逻辑，巧妙结合前沿探索与选择性预判，在无需对节点进行全局排序的前提下，实现了比最优Dijkstra算法更快的运行速度。这一成果不仅解决了图论中的核心难题，更重新定义了我们对路径搜索效率的认知边界。

关键词：最短路径问题、排序障碍、图论、Dijkstra算法、Bellman-Ford算法、随机算法（randomized algorithm）、算法优化

文章题目：New Method Is the Fastest Way To Find the Best Routes

文章地址：https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/

文章来源：Quanta magazine

打破四十年瓶颈：

新算法突破最短路径“排序障碍”

如果你想解决一个棘手的问题，事先做好规划通常会有所帮助。例如，你可以将问题分解成若干部分，并优先处理最容易的部分。但这种排序本身是有代价的：你最终可能会花费过多时间来对各个部分进行排序。

这种困境在计算机科学中最著名的难题之一中尤为突出：即从网络中的某个特定起点出发，寻找通往所有其他点的最短路径。这类似于你每次搬家后都需要解决的问题的“升级版”——学习从新家到工作单位、健身房和超市的最佳路线。

“最短路径问题是如此优美，世界上任何人都能理解它的意义。”

——哥本哈根大学的计算机科学家Mikkel Thorup

直观上，找到通往附近目的地的最短路径应该是最容易的。因此，如果你想要设计出求解最短路径问题的最快算法，从最近的点开始，然后依次处理第二近、第三近的点，似乎是合理的策略。但要做到这一点，你必须反复判断哪个点是当前最近的，这意味着你将一边处理一边按距离对点进行排序。对于采用这种策略的任何算法而言，存在一个根本性的速度极限：其运行速度不可能快于排序所需的时间。

四十年前，设计最短路径算法的研究人员就遇到了这一排序障碍（sorting barrier）。如今，一组研究人员设计出了一种突破该障碍的新算法。它不进行排序，且运行速度超过了任何依赖排序的算法。

“作者们敢于设想能够打破这一障碍，这种勇气令人钦佩，这是一个令人惊叹的成果。”

——普林斯顿大学的计算机科学家Robert Tarjan

知识的边界

为了从数学上分析最短路径问题，研究人员使用图论（graph theory）的语言：即由点（或称节点，node）通过线连接而成的网络。每条连接节点的边都标有一个称为权重（weight）的数值，它可以表示该段路径的长度或通过该路径所需的时间。任意两个节点之间通常存在多条路径，其中总权重最小的路径即为最短路径。给定一个图和一个特定的“源点”（source node），算法的目标就是找到从该源点到所有其他节点的最短路径。

最著名的最短路径算法是由先驱计算机科学家Edsger Dijkstra于1956年提出的Dijkstra算法。该算法从源点出发，逐步向外扩展。这是一种高效的方法，因为掌握到附近节点的最短路径有助于进一步发现更远节点的最短路径。然而，由于最终结果是一个按距离排序的最短路径列表，因此排序障碍对算法的运行速度设定了一个根本性的限制。

Edsger Dijkstra提出了一种经典算法，用于寻找网络中从某一特定点到所有其他点的最短路径。

1984年，Tarjan与另一位研究人员改进了Dijkstra原始算法，使其达到了这一速度极限。任何进一步的提升必须依赖于一种避免排序的算法。

在20世纪90年代末到21世纪初，Thorup和其他研究人员设计出了一些能够突破排序障碍的算法，但他们需要对边的权重（weights）做出某些特定假设。当时无人知道如何将这些技术推广到任意权重的情形，研究似乎已经走到了尽头。

“这项研究停滞了非常长的时间，”北京清华大学的计算机科学家段然说，“许多人认为已经没有更好的方法了。”

段然却不这么认为。他长期以来一直梦想构建一种能够在所有图上突破排序障碍的最短路径算法。去年秋天，他终于成功了。

段然，清华大学交叉信息研究院副教授

摆脱排序的束缚

段然对排序障碍的兴趣可追溯到近20年前他在密歇根大学攻读研究生时期，当时他的导师正是在特定情况下突破该障碍的研究者之一。但直到2021年，段然才设计出一种更具前景的新方法。

关键在于关注算法在每一步中下一步的探索方向。Dijkstra算法会利用之前步骤中已探索的区域，并通过扫描该区域的“边界”（frontier）——即所有与边界相连的节点——来决定下一步的走向。起初这不会耗费太多时间，但随着算法的推进，其速度会逐渐变慢。

段然则设想将前沿上的相邻节点分组为若干簇（clusters），然后仅从每个簇中选取一个节点进行考虑。由于需要筛选的节点数量减少，每一步的搜索速度得以提升。此外，该算法可能不会总是选择最近的节点，因此“排序障碍”不再适用。然而，确保这种基于聚类的方法确实能提升而非降低算法效率，仍是一个挑战。

在接下来的一年里，段然不断完善这一基本构想，到2022年秋季，他已乐观地认为自己能够克服技术上的重重障碍。他邀请了三名研究生加入团队，协助完善细节。几个月后，他们取得了一项阶段性成果——一种新算法：该算法在任意权重下均能突破排序障碍，但仅适用于所谓的非定向图（undirected graph）。

文章题目：A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs

文章地址：https://arxiv.org/pdf/2307.04139

在非定向图中，每条连接（边）都可以双向通行。然而，计算机科学家通常更关注一类更广泛的图，即包含单向路径的图，这类定向图（directed graph）往往更难处理。

“可能存在这样一种情况：A很容易到达B，但B却很难到达A，”斯坦福大学的计算机科学研究生毛啸解释道，“这会给你带来很多麻烦。”

充满希望的路径

2023年夏天，毛啸在加州的一次会议上听到段然介绍其在非定向图上的算法。他主动与段然交谈，而后者的工作一直是他长期钦佩的研究人员。

会后，毛啸开始在业余时间思考这个问题。与此同时，段然及其同事正在探索适用于定向图的新方法。他们从另一个著名的最短路径算法——Bellman-Ford算法中获得灵感，该算法不生成排序列表。乍看之下，这似乎是一个不明智的策略，因为Bellman-Ford算法比Dijkstra算法慢得多。

段然的团队通过仅运行Bellman-Ford算法的少数几步，避免了其整体运行缓慢的问题。这种选择性使用使他们的算法能够提前“侦察”后续步骤中最有价值的节点。这些节点类似于道路网络中主干道的交汇点。

2024年3月，毛啸想到了另一种有前景的方法。团队原始方法中的某些关键步骤使用了随机性。虽然随机算法（randomized algorithm）能高效解决许多问题，但研究人员仍更倾向于非随机方法。毛啸设计了一种无需随机性的新方法来解决最短路径问题。他随后加入团队，通过群聊和视频会议与团队成员合作数月，融合各方思路。

最终在秋季，段然意识到他们可以借鉴自己在2018年为另一图论问题设计的、曾突破排序障碍的算法技术。这项技术正是他们构建在定向图和非定向图上均快于Dijkstra算法所需的关键拼图。

文章题目：Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

文章地址：https://arxiv.org/abs/2504.17033

最终的算法将图分层，像Dijkstra算法一样从源点向外扩展。但与每一步都处理整个前沿不同，该算法利用Bellman-Ford算法定位关键影响节点，从这些节点向前推进以寻找通往其他节点的最短路径，之后再回过头处理其他前沿节点。它并不总是按距离递增的顺序找出每一层的节点，因此排序障碍不再适用。只要以恰当方式对图进行分割，该算法的运行速度就略快于最优版本的Dijkstra算法。尽管结构更为复杂，依赖多个组件的精密配合，但有趣的是，其中并未使用任何高深的数学。

“这个算法五十年前就有可能被发现，但实际上却没有，这反而使它的诞生更加令人印象深刻。”

——哥本哈根大学的计算机科学家Mikkel Thorup

段然及其团队计划进一步探索该算法是否还能被简化以实现更快速度。随着排序障碍的破除，新算法的运行时间尚未接近计算机科学家所知的任何根本性极限。

“作为一个乐观主义者，如果还能进一步降低运行时间，我也不会感到惊讶，我当然不认为这是该过程的最后一步。”

——普林斯顿大学的计算机科学家Robert Tarjan