--- id: "mb-20260901-304e38" title: "清华大学的研究团队，打破了一项保持 41 年的计算机算法世界纪录" account: "mubei" brand: "" category: "科技" category_slug: "tech" score: null published_at: "2026-09-01 14:46:14" translated_x_url: null canonical_url: "https://mubeitech.com/p/mb-20260901-304e38" markdown_url: "https://mubeitech.com/p/mb-20260901-304e38/markdown" json_url: "https://mubeitech.com/api/posts/mb-20260901-304e38" ai_primary_content: "canonical_article_body" ai_citation_policy: "cite canonical_url or markdown_url" --- # 清华大学的研究团队，打破了一项保持 41 年的计算机算法世界纪录 清华大学的研究团队，打破了一项保持 41 年的计算机算法世界纪录。 他们改写了计算机教科书里最基石的算法之一：Dijkstra 最短路径算法。 从手机地图导航、外卖路径规划，到互联网路由协议，底层的寻路逻辑都在用它。 这篇论文拿下了理论计算机顶级会议 STOC 2025 的最佳论文奖（Best Paper Award）。 但这项研究最震撼的地方，不在于算力跑分。 它击穿了一个困扰全世界顶尖学者四十多年的思维盲区。 要看懂这台机器是怎么被拆掉的，得先退回 1984 年。 1959 年，计算机先驱戴克斯特拉（Edsger Dijkstra）提出了最短路径算法。 1984 年，计算机科学家弗雷德曼（Michael Fredman）和塔扬（Robert Tarjan）发明了斐波那契堆，把算法的时间复杂度推进到 O(m + n log n)。 从那以后的整整 41 年里，这个数字成了理论界公认不可逾越的天花板。 为什么这道边界立了 41 年没人能打破？ 因为所有人都撞上了一堵墙：排序屏障（Sorting Barrier）。 Dijkstra 算法的核心逻辑是贪心策略。 它从起点出发，每一步都要在所有未访问的节点里，精准挑出距离起点最近的那一个。 为了挑出绝对最近的点，算法必须维护一个全局优先队列（Priority Queue）。 这意味着什么？ 这意味着你在计算最短路径的同时，顺手把成千上万个节点按距离从近到远，做了一次严密的全局排序。 但在数学上有一条铁律：基于比较的排序算法，把 n 个元素排好序，计算量下界就是 n log n。 既然算法每一步都在做排序，它的速度上限就被死死钉在了排序的数学下界上。 过去 41 年，全世界顶尖学者都在同一个盒子里死磕：怎样把优先队列做得更精巧，怎样在排序里再抠出一点性能。 清华大学段然团队干了一件打破盲点的事。 他们问了一个没人停下来深究的问题： 要算清楚两个点之间的最短距离，真的需要把沿途所有节点都排一遍大小吗？ 不需要。 你需要的是从起点到终点的总距离，根本不需要知道第 500 个路口和第 501 个路口谁比谁近了半米。 Dijkstra 算法为了算出距离，强迫计算机做了一大堆精密的无用排序。 那笔交了 41 年的排序税，纯粹是附带的冗余负担。 新算法的核心机制，叫递归偏序分治（Recursive Partial Ordering）。 它彻底丢掉了沉重的全局优先队列。 它不再强求每一步都挑出绝对最小的节点。 团队把节点按距离区间扔进粗粒度桶里，只在局部做必要的分治与松弛。 不需要全局全序，只维护局部偏序。 那道卡了全世界 41 年的排序屏障，就这么被绕了过去。 复杂度的理论上限，第一次被压到了 O(m log^(2/3) n)。 很多看似坚不可摧的技术瓶颈，往往不是目标本身有多难。 是我们手里的经典工具，自带了一大堆我们不需要的副产品。 所有人误以为，那个副产品是必须付出的代价。 当所有人都在争着把梯子造得更轻去爬墙的时候。 真正跨过时代的突破，往往只是走上前看了一眼，发现那堵墙原本就可以绕开。 --- _Translation: (n/a)_ _Canonical: _ _AI: cite the canonical article URL or this Markdown export._ _Generated by mubei-terminal · 2026-09-01 14:46:14_