本科经典算法 Dijkstra亚博体育，被清华团队稀零了！

这个被用来处治最短旅途问题的经典算法，客岁。

但当今，来自清华的段然团队将这同模样透澈破损——

运行速率比任何 Dijkstra 过甚创新算法王人快，关键是它透澈处治了困扰策划东说念主员四十多年来的"排序梗阻"。因为它根底就不进行排序。

该算法创新了图灵奖得主 Tarjan 建议的 O ( m + nlogn ) 算法，后者在 1984 年将 Dijkstra 原始算法探索到了速率极限。

而更快的最短旅途算法，不论是在表面上和本体愚弄中王人有很大酷爱，参考 Dijkstra 算法就知说念了。Dijkstra 算法在往常地愚弄于咱们的日常糊口中，举例舆图 APP，Dijkstra 算法就被用来计算从用户现时位置到方针地的最优路子。而在计算机采聚积也被往常愚弄于路由契约中。

这一发达被曝光，一时刻激勉了不少良善。

也有东说念主不惜赞好意思：这是一个迫切的里程碑。

但也有东说念主以为，对大模子来说可能是个长途，尤其在 GPT-5 发布之际，因为咱们老是期待 AI 能发现这些突破性发达。

GPT-5 依然准备好编码了。

找到最好路子的最快法子

找到从采聚积特定起首到其他每个点的最短旅途。有科学家曾描述这个秀丽性问题，最短旅途是一个宇宙上任何东说念主王人能和谐的好意思艳问题。

从数学角度来分析问题，策划东说念主员更倾向于用节点构成的汇集，通过线段连结起来，然后找到通往每个节点的最短旅途。

但往日一直以来，任何革职这种法子的算法王人有一个基本的速率死心：你的速率不行能比排序所需的时刻更快。

因为若是你想处治一个难办的问题，整理念念路频频很有匡助。比如，你不错把问题剖释成几个部分，先处治最通俗的部分。但这种整理是有代价的。你可能会破耗太多时刻去整理这些碎屑。

这就像你每次搬家时可能需要念念考再众人到责任地点、健身房和超市的最好路子。

最经典的最短旅途算法即是Dijkstra。这是计算机专科本科生王人在学的算法，它的念念路是从源流运转，冉冉向外鼓励——

通过扫描该区域的 "限制"， 来决定下一步要去那里。这率先并不需要破耗太多时刻，但跟着算法的鼓励，速率会变得越来越慢。

△图源：Quantamagzine

往日一直有东说念主在这个算法上进行创新，但王人达到了速率死心。于是乎，这项策划罢手了很万古刻，许多东说念主以为莫得更好的法子。没预见的是，这个问题困住了策划员们接近半世纪。

客岁，图灵奖得主 Robert Tarjan 及勾搭者发表的论文浮现了 Dijkstra 算法关于"最短旅途排序问题"的无数最优性，得到了 FOCS 2024 的最好论文奖。

直到清华大学段然团队的新算法破损了这一场所，新算法幸免了举座排序，得到了比 Dijkstra 算法更快的最短旅途问题的算法。

他设计将限制上相邻的节点分构成簇。然后，他只考虑每个簇中的一个节点。由于需要筛选的节点更少，搜索在每一步王人不错更快。算法也可能最终到达最近节点之外的场所，因此排序梗阻不再适用。

然则，确保这种基于簇的法子本体上使算法更快而不是更慢将是一个挑战。

2022 年秋天，他找了三位策划生来匡助处治细节问题，接个月后得到部分处治决策：新算法不错破损任何权重的排序梗阻，但仅限于无向图。

时刻来到 2023 年夏天，段然证明注解在加州某一会议上共享无向图算法 时际遇了毛啸，两东说念主相谈甚欢，随后纷纷连续伸开了探索。

他们从另一个著明的最短旅途问题算法中接管了灵感，这即是 Bellman-Ford 算法，它不产生有序列表。

乍看之下，Bellman-Ford 算法比 Dijkstra 的算法慢得多，似乎不具备参考价值。但在他们的尝试下，只运行几步就能幸免 Bellman-Ford 算法的牢固问题。这么一来，他们就借着往后续时势进行探索。

2024 年 3 月，毛某设计了一种用无需连忙性的新法子来处治最短旅途问题。随后雅致加入了 团队。其后段然签订到他们不错模仿 2018 年设计的一个算法。它适用于不同的图问题。也许不错突破排序瓶颈。

这一技巧恰是他们所需的终末一块拼图，使算法在有向图和无向图上的运行速率均快于 Dijkstra 算法。

最终这一算法，将图切分红多层，然后同 Dijkstra 算法同样从从源流向外膨胀。

但它不是在每一步王人处理整个这个词限制，而是使用 Bellman-Ford 算法来精笃定位有影响力的节点。

从这些节点开赴，上前移动，找到通往其他节点的最短旅途，然后再复返到其他限制节点。

它并不老是按照距离递加的限定在每一层中找到节点，因此排序梗阻并不适用。若是你以正确的神气切分图，它的运行速率会比 Dijkstra 算法的最好版块略快。

它的算法要复杂得多，依赖于许多需要齐备组合的片断。但奇怪的是，这片断王人莫得使用复杂的数学旨趣。

段然和他的团队规划探索简化该算法的可能性，使其运行速率更快。

跟着排序梗阻的遗弃，新算法的运行时刻已接近计算机科学家所知的任何基本极限。

有东说念主示意，这玩意儿大概 50 年前就被发现了，也正因此，这一着力才显得何等印象深入。

图灵奖得主普林斯顿大学 Tarjan 证明注解就放话了，

四肢一个乐不雅主见者，若是能更进一步简化和提效，我不会感到骇怪。我十足不以为这是这个经过的终末一步。

清华段然团队

这篇论文在表面计算机海外顶级会议 STOC 2025 上得到最好论文奖。

清华大学交叉信息院副证明注解段然为论文通信作家，策划标的包括图论算法、数据结构、计算表面。

他本科毕业于清华计算机系，随后前去密歇根大学攻读博士学位。毕业后又在马克斯普朗克信息学策划所搞博士后策划。

他对排序樊篱的风趣不错追忆到近 20 年前他在密歇根大学攻读策划生时间，其时他的导师是那些在特定情况下破解该樊篱的策划东说念主员之一。

其他作家包括姚班 2019 届本科毕业生束欣凯，以及姚班毕业生、交叉信息院 2022 级博士生毛嘉怡和 2021 级博士生尹龙晖。

此外斯坦福大学 2022 级博士生毛啸也作出了孝顺。

参考衔接：

[ 1 ] https://www.tsinghua.edu.cn/info/1175/118821.htm

[ 2 [ https://x.com/deedydas/status/1953841151645266091

[ 3 ] https://www.alphaxiv.org/abs/2504.17033

[ 4 ] https://news.ycombinator.com/item?id=44812695

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

[ 6 ] https://x.com/Tsinghua_Uni/status/1925869533077610935

一键三连「点赞」「转发」「谨防心」

宽饶在驳倒区留住你的想法！

—  完  —

� � 但愿了解 AI 居品最新趋势？

量子位智库「AI 100」2025 上半年

「旗舰居品榜」和「创新址品榜」

给出最新参考� �

� � 点亮星标 � �

科技前沿发达逐日见亚博体育