突破40年Dijkstra算法瓶颈，清华教授等颠覆教科书！斩获STOC最佳论文

新智元报道

编辑：KingHZ

【新智元导读】清华大学教授段然提出了一种最短路径新方法，击败了教科书中经典的Dijkstra算法。

计算机科学的重大成果！

清华大学教授刷新最短路径算法认知，或将改写计算机算法教科书。

在计算机科学中，一个经典问题是寻找网络中每个点的最短路径，而Dijkstra算法是此问题的最经典解决方法。

自1956年来，最短路径问题吸引了众多研究人员的关注。

哥本哈根大学计算机科学家Mikkel Thorup米克尔·索鲁普表示:

最短路径是个绝妙的好问题，全世界人都能感同身受。

直觉上，找到离起点最近的点的路径应该最简单。

因此，如果想设计一个解决最短路径问题的最快算法，合理的做法是先找到最近的点，然后是次近的点，依此类推。但这意味着你需要反复确定哪个点是最近的，也就是说，你得按距离给这些点排序。

然而，这种方法有一个根本的限制：这种算法的速度无法快过排序所需的时间。

四十年前，研究最短路径算法的科学家们遇到了这个「排序瓶颈」。

现在，来自清华大学等机构的研究团队设计了一种新算法，突破了这一瓶颈。这种算法不依赖排序，而且比任何需要排序的算法运行得更快。

论文链接：https://arxiv.org/abs/2504.17033

普林斯顿大学的计算机科学家Robert Tarjan说：「这些研究者大胆地认为他们能打破这个瓶颈。这是一个惊艳的成果。」

值得一提的是，这项研究摘得STOC最佳论文，实至名归。

左：Mikkel Thorup；右：Robert Tarjan

最短路径

若想解决复杂难题，条理分明往往事半功倍。比如将问题拆解后优先处理最简单的部分——但这种分类需要代价，你可能耗费过多时间在排序上。

这一困境尤其体现在计算机科学中最经典的问题之一：如何在网络中从特定起点出发，找到通往其他所有点的最短路径。这就像日常搬家后必须解决的升级版问题：规划从新家到公司、健身房和超市的最佳路线。

为了从数学角度分析最短路径问题，研究者们使用图论的语言——图是由点（或称节点）组成的网络，这些点通过线连接起来。每条连接线都标有一个数字，叫作权重，它可以代表这段线的长度或穿越它所需的时间。

通常，任意两个节点之间都有很多路径，最短路径就是那些权重加起来最小的路径。给定一个图和一个特定的「起点」，算法的目标就是找到到其他每个节点的最短路径。

在1956年，计算机科学先驱埃兹赫·迪杰斯特拉（Edsger Dijkstra）设计了日后最著名的最短路径算法。

它从起点开始，一步步向外扩展。

Dijkstra算法如何找到最短路径

Dijkstra算法从网络中的一个特定点开始，找到到每个其他点的最短路径。它按距离从近到远的顺序找到这些路径。

Dijkstra算法的基本步骤：

从A点开始：

你看到两条路径。B点距离1单位，C点距离5单位。你现在知道到B的最短路径，但可能有一条更短的间接路径到C。 最短路径：A → B = 1

跟随最短路径：

前往 B，然后再观察一次，记录从 A 到每个点的总距离。D点比C点离 A 更近。最短路径：A → B = 1；A → D = 2

继续探索:

前往D点并再次观察，现在你已经找到了到C的最短路径。最短路径 ：A → B = 1；A → D = 2；A → C = 3。

从起点开始，逐步探索网络中到每个点的最短路径——这种方法很有效，因为知道到附近节点的最短路径，能帮助你找到到更远节点的最短路径。

但最终结果是一个按距离排序的最短路径列表，因此排序瓶颈设定了算法速度的根本限制。

1984年，Tarjan和另一位研究者改进了迪杰斯特拉的原始算法，使其达到了这个速度极限。任何进一步的改进都必须来自一个避免排序的算法。

论文链接：https://dl.acm.org/doi/10.1145/28869.28874

在20世纪90年代末和21世纪初，Thorup和其他研究者设计出了打破排序瓶颈的算法。

从左至右：Bernhard Haeupler、Václav Rozhoň（上方）、Jakub Tětek（下方）、Robert Tarjan和Richard Hladík证明了Dijkstra算法的一个版本是对所有网络布局的最佳解决方案

他们需要对权重做出某些假设。没人知道如何将这些技术扩展到任意权重上。似乎他们已经走到了尽头。

研究停滞了很长一段时间，很多人相信没有更好的办法了。

但清华的段然不是其中之一。他长期梦想构建一个能在所有图上突破排序瓶颈的最短路径算法。去年秋天，他终于成功了。

超越排序

段然对排序瓶颈的关注可以追溯到近20年前。

那时，他在密歇根大学读研究生。他的导师是研究如何在特定情况下打破排序瓶颈的学者之一。

但直到2021年，段然才找到一个更有前景的方法。

关键在于关注算法每一步的下一步走向。

迪杰斯特拉的算法会利用之前已探索的区域，决定下一步通过扫描这个区域的「边界」——也就是所有与边界相连的节点。起初这不会花太多时间，但随着算法推进，速度会变慢。

段然则设想将边界上的相邻节点分组，形成多个集群。每一步只考虑每个集群中的一个节点。由于需要筛选的节点减少了，每一步的搜索都能更快。算法可能不会总是选择最近的节点，因此排序瓶颈不再适用。但要确保这种基于集群的方法确实能加速算法，而不是让它更慢，是一个挑战。

在接下来的一年里，段然完善了这个基本想法。

到2022年秋天，他乐观地认为自己能克服技术难题。

他拉来三位研究生帮忙细化细节，几个月后，他们取得了部分成功——开发出了一种算法，打破了任意权重下的排序瓶颈，但仅适用于所谓无向图。

论文链接：https://arxiv.org/abs/2307.04139

在无向图中，每条连接线都可以双向通行。计算机科学家通常更关注包含单向路径的更广义的图类，但这些「有向图」往往更难处理。

这次新论文的合著者、斯坦福大学计算机科学博士生毛啸说：「（在有向图中）可能存在一种情况，A到B很容易，但B到A却很困难。这会给你带来很多麻烦。」

希望之路

2023年夏天，在加州的一场学术会议上，毛啸聆听了段然关于无向图算法的演讲。他主动与这位仰慕已久的学者攀谈起来。

那是他第一次在现实中见到段然，当时非常激动。

随机性如何优化算法

会议结束后，毛啸开始利用业余时间思考这个问题。与此同时，段和他的团队正在探索适用于有向图的新方法。他们从最短路径问题的另一经典算法——贝尔曼-福特算法中汲取灵感。

贝尔曼-福特算法不生成排序列表，但初看却像是个糟糕的选择：它的速度远逊于迪杰斯特拉算法。

计算机科学家米克尔·索鲁普补充道：「科研就是不断尝试有潜力的路径。但借鉴贝尔曼-福特算法简直像在反其道而行——这看起来蠢透了。」

段然的团队通过分阶段运行贝尔曼-福特算法避开了其低速缺陷。这种选择性使用让他们能预先侦察后续步骤中最有价值的节点，这些节点如同交通网络中的核心枢纽。

计算机科学家米克尔·索鲁普解释道：「要获取多数目的地的最短路径，你必须经过这些关键点」。

2024年3月，毛啸提出另一创新思路。

原算法中某些关键步骤依赖随机性，虽然随机算法能高效解决许多问题，但学界仍更青睐确定性方案。

毛啸设计出无需随机化的最短路径求解方法，随后加入团队。

通过数月的群聊和视频会议，他们最终在秋季取得突破——段然教授意识到可借鉴其2018年解决另一类图问题时突破排序障碍的技术，这正是补齐最后一块拼图的关键。

层进式革新

最终算法将图分层处理，像迪杰斯特拉算法那样从源头向外推进。

但其精妙之处在于：通过贝尔曼-福特算法定位关键节点后优先探索，稍后回溯处理其他边界节点。由于不严格按距离顺序探索每层节点，排序障碍自然失效。若采用恰当的分层策略，其速度甚至略超优化版迪杰斯特拉算法。

这个由多个精密模块组成的算法虽复杂，却意外地未使用任何高深数学工具。

计算机科学家米克尔·索鲁普感慨万分：「这套方法本可能在五十年前就被发现，但直到现在才问世。这才更显其非凡。」

段然团队正着手优化算法以追求更快的速度。随着排序障碍的攻克，新算法的运行效率已远超现有理论极限。

参考资料：

https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/

https://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html

https://iiis.tsinghua.edu.cn/en/People/Faculty/DuanRan.htm