本科经典算法 Dijkstra开yun体育网，被清华团队超过了！

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

但当今，来自清华的段然团队将这相同式透澈冲突——

运行速率比任何 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 上半年

「旗舰产物榜」和「翻新产物榜」

给出最新参考� �

� � 点亮星标 � �

科技前沿发达逐日见开yun体育网