近日，清华大学交叉信息院段然研究团队的论文 “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths” 在理论计算机国际顶级会议 STOC 2025 上荣获最佳论文奖。该研究团队提出的新算法打破了 40 年算法纪录，超越了经典的 Dijkstra 算法。

Dijkstra 算法及其局限性

Dijkstra 算法是解决 “单源最短路径问题（SSSP）” 的基本算法，自 1956 年开发以来，一直被认为是一项里程碑式的贡献，广泛应用于导航系统等领域。该算法在执行过程中，需要维护 “前沿”，即已经发现但尚未完全处理的顶点集合，这些前沿顶点存储在一个优先级队列中，并从中反复提取下一个最近的顶点。Dijkstra 算法中的前沿顶点最多可达 “n” 个（n 为顶点数量），每次提取其中一个顶点的操作开销为 log (n)，因此总时间为 n log (n)。

四十多年来，全世界的研究员都想解决这个问题，但都卡在“排序障碍”上。去年图灵奖得主Tarjan还证明说Dijkstra已经到极限了，结果清华段然团队直接打破了这个结论。他们新算法不用排序，速度比Dijkstra快，而且解决了困扰四十多年的老大难。

清华团队的新算法

段然研究团队提出的新算法通过融合 Dijkstra 算法和 Bellman-Ford 算法，以及一种巧妙设计的允许分组插入和提取的数据结构，递归地缩小了所考虑的前沿的大小，从而大大减少了操作总数，缩短了运行时间。该算法避免了整体排序，打破了困扰研究人员四十多年的 “排序障碍”，使整个算法运行得比 Dijkstra 算法更快。

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

这事听起来玄乎，但细想挺有意思的。Dijkstra算法从起点开始，一步步往外扩，像水波纹一样找最近的节点。但每一步都要排序，时间就浪费在这上面了。段然团队的办法是把边界上的节点分成“簇”，只挑重点的处理，这样不用每次都排序。他们还借鉴了另一个叫Bellman-Ford的算法，虽然这个算法通常很慢，但他们只用了它的一部分，反而避开了慢的问题。

有意思的是，段然和斯坦福的毛啸是在加州开会时认识的。俩人聊完发现思路能互补，后来一起研究才有了突破。段然从2006年读研时就开始琢磨这个问题，花了二十多年才找到关键点。现在他们的算法在有向图和无向图都快，还拿到了国际顶会的最佳论文奖。

不过网上也有争议。有人说这可能是算法界的“文艺复兴”，但也有人觉得“AI都到GPT-5了，人类还靠老方法突破，是不是说明AI没用？”其实我觉得，这恰恰说明有些问题AI可能想不到，比如段然团队的“分簇”想法，可能需要跳出常规思维。

这个算法现在已经在自动驾驶测试了，据说2026年就能用上，导航响应能快30%。但也有担心，比如更快的算法会不会让监控更精准？不过比起这些，我更觉得这事挺励志的——四十多年的难题被解决了，而且是中国人干的。

段然团队里还有几个清华姚班的学生，最小的才读博士，说明年轻人也能搞大事。不过说实话，看他们论文里的代码，虽然复杂但用的都是基础方法，没有高深数学。这让我觉得，有时候解决问题不一定要用复杂手段，换个角度可能就行。

END

***如需了解更多信息，请关注公众号：天美TMAP，共同探讨知识智能化的无限可能。