祝贺！清华段然研究团队获国际顶级会议STOC 2025最佳论文奖——突破经典Dijkstra 算法

[ql2015]

这个厉害

实际用途太大了，这个才是最短路径的普遍最优解

土鳖搞实际应用，能力太强了

麻痹的，当初本帝学计算机算法的时候，用的是MIT的书，也曾经想过Dijkstra到底是不是普遍最优解，但是无从下手思考...

突破了一个沉睡了差不多一个世纪的算法。 很牛B。
应该能得图灵奖吧，拭目以待

[none]

祝贺！

https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（SSSP）”。Dijkstra 算法是解决这一问题的基本算法，它以荷兰计算机科学家 Edsger Dijkstra 的名字命名。自 1956 年开发以来，该算法一直被认为是一项里程碑式的贡献，被广泛应用于导航系统等。为了改进 Dijkstra 算法，该论文仔细研究了造成其大部分计算成本的部分：与所谓 “优先队列 ”的交互。在执行过程中，Dijkstra 算法需要维护 “前沿”，即已经发现但尚未完全处理的顶点集合--这意味着它们与源点的暂定最短距离是已知的，但算法可能尚未完全探索它们的邻近顶点。这些前沿顶点存储在一个优先级队列中，并从中反复提取下一个最近的顶点。Dijkstra 算法中的前沿顶点可以多达 “n”，即顶点的数量。每次提取其中一个顶点的操作开销为 log(n)，因此总时间为 n log(n)。研究团队提出的新算法通过融合Dijkstra算法和Bellman-Ford的教科书算法，以及一种巧妙设计的允许分组插入和提取的数据结构，递归地缩小了所考虑的前沿的大小。因此，操作的总数可以大大减少，从而缩短了运行时间，使整个算法运行得更快。

2024年图灵奖得主Robert Tarjan及合作者发表的论文证明了Dijkstra算法对于“最短路径排序问题”的普遍最优性，获得了FOCS 2024的最佳论文奖，受到了Quanta Magazine和量子位等媒体的报道。单源最短路径问题需要找到从一点s到其他所有点的最短路，而Dijkstra算法的副产品是所有点按照从源点的距离排序，也就是说他们证明的是Dijkstra算法对于这个排序问题是普遍最优的（universally optimal）。但段然组的新算法避免了整体排序，所以得到了比Dijkstra算法更快的最短路径问题的算法。而且最短路径问题明显更加重要，更快的最短路径算法在理论上和实际应用中都有很大意义。

本论文通讯作者为段然副教授，其他作者包括姚班2019届本科毕业生束欣凯，以及姚班毕业生、交叉信息院2022级博士生毛嘉怡和2021级博士生尹龙晖，此外还有斯坦福大学2022级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

[big5]

https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（SSSP）”。Dijkstra 算法是解决这一问题的基本算法，它以荷兰计算机科学家 Edsger Dijkstra 的名字命名。自 1956 年开发以来，该算法一直被认为是一项里程碑式的贡献，被广泛应用于导航系统等。为了改进 Dijkstra 算法，该论文仔细研究了造成其大部分计算成本的部分：与所谓 “优先队列 ”的交互。在执行过程中，Dijkstra 算法需要维护 “前沿”，即已经发现但尚未完全处理的顶点集合--这意味着它们与源点的暂定最短距离是已知的，但算法可能尚未完全探索它们的邻近顶点。这些前沿顶点存储在一个优先级队列中，并从中反复提取下一个最近的顶点。Dijkstra 算法中的前沿顶点可以多达 “n”，即顶点的数量。每次提取其中一个顶点的操作开销为 log(n)，因此总时间为 n log(n)。研究团队提出的新算法通过融合Dijkstra算法和Bellman-Ford的教科书算法，以及一种巧妙设计的允许分组插入和提取的数据结构，递归地缩小了所考虑的前沿的大小。因此，操作的总数可以大大减少，从而缩短了运行时间，使整个算法运行得更快。

2024年图灵奖得主Robert Tarjan及合作者发表的论文证明了Dijkstra算法对于“最短路径排序问题”的普遍最优性，获得了FOCS 2024的最佳论文奖，受到了Quanta Magazine和量子位等媒体的报道。单源最短路径问题需要找到从一点s到其他所有点的最短路，而Dijkstra算法的副产品是所有点按照从源点的距离排序，也就是说他们证明的是Dijkstra算法对于这个排序问题是普遍最优的（universally optimal）。但段然组的新算法避免了整体排序，所以得到了比Dijkstra算法更快的最短路径问题的算法。而且最短路径问题明显更加重要，更快的最短路径算法在理论上和实际应用中都有很大意义。

本论文通讯作者为段然副教授，其他作者包括姚班2019届本科毕业生束欣凯，以及姚班毕业生、交叉信息院2022级博士生毛嘉怡和2021级博士生尹龙晖，此外还有斯坦福大学2022级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

论坛里那么多高知咋就看不出个所以然
就是做了一些约束性的假设，并对Dijkstra 算法在约束性假设情况下做了优化
典型的灌水文，学术圈的入门级玩法

[dawangzi]

牛逼2

[harubashi]

论坛里那么多高知咋就看不出个所以然
就是做了一些约束性的假设，并对Dijkstra 算法在约束性假设情况下做了优化
典型的灌水文，学术圈的入门级玩法

你得到了它，清华这个团干大学，精致利己是第一位的，research和生意是一回事儿。

这事儿背后dig一下，一定有行贿STOC OC, 用钱和年轻噗湿收买评委的情节。

[harubashi]

牛逼2

文科生，你好。

[datada]

re

[viczhang]

论坛里那么多高知咋就看不出个所以然
就是做了一些约束性的假设，并对Dijkstra 算法在约束性假设情况下做了优化
典型的灌水文，学术圈的入门级玩法

感觉是的

[fieldman]

AI打破了索南写论文的英语障碍，现在只要有思想有成就，很快就能传遍天下，突破昂撒人靠语言建立起来的学术霸权。

https://mp.weixin.qq.com/s?__biz=MzAxMDg0OTUxNw==

近日，清华大学交叉信息院段然研究团队的论文“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”在理论计算机国际顶级会议STOC 2025（ACM SIGACT Symposium on Theory of Computing）上荣获最佳论文奖。

段然研究团队探讨了图论算法中经典的“单源最短路径问题（SSSP）”。Dijkstra 算法是解决这一问题的基本算法，它以荷兰计算机科学家 Edsger Dijkstra 的名字命名。自 1956 年开发以来，该算法一直被认为是一项里程碑式的贡献，被广泛应用于导航系统等。为了改进 Dijkstra 算法，该论文仔细研究了造成其大部分计算成本的部分：与所谓 “优先队列 ”的交互。在执行过程中，Dijkstra 算法需要维护 “前沿”，即已经发现但尚未完全处理的顶点集合--这意味着它们与源点的暂定最短距离是已知的，但算法可能尚未完全探索它们的邻近顶点。这些前沿顶点存储在一个优先级队列中，并从中反复提取下一个最近的顶点。Dijkstra 算法中的前沿顶点可以多达 “n”，即顶点的数量。每次提取其中一个顶点的操作开销为 log(n)，因此总时间为 n log(n)。研究团队提出的新算法通过融合Dijkstra算法和Bellman-Ford的教科书算法，以及一种巧妙设计的允许分组插入和提取的数据结构，递归地缩小了所考虑的前沿的大小。因此，操作的总数可以大大减少，从而缩短了运行时间，使整个算法运行得更快。

2024年图灵奖得主Robert Tarjan及合作者发表的论文证明了Dijkstra算法对于“最短路径排序问题”的普遍最优性，获得了FOCS 2024的最佳论文奖，受到了Quanta Magazine和量子位等媒体的报道。单源最短路径问题需要找到从一点s到其他所有点的最短路，而Dijkstra算法的副产品是所有点按照从源点的距离排序，也就是说他们证明的是Dijkstra算法对于这个排序问题是普遍最优的（universally optimal）。但段然组的新算法避免了整体排序，所以得到了比Dijkstra算法更快的最短路径问题的算法。而且最短路径问题明显更加重要，更快的最短路径算法在理论上和实际应用中都有很大意义。

本论文通讯作者为段然副教授，其他作者包括姚班2019届本科毕业生束欣凯，以及姚班毕业生、交叉信息院2022级博士生毛嘉怡和2021级博士生尹龙晖，此外还有斯坦福大学2022级博士生毛啸。





论文原文：Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (2025): „Breaking the Sorting Barrier for Directed Single-Source Shortest Paths“. 57th Annual ACM Symposium on Theory of Computing (STOC).

[Rabboni]

你得到了它，清华这个团干大学，精致利己是第一位的，research和生意是一回事儿。

这事儿背后dig一下，一定有行贿STOC OC, 用钱和年轻噗湿收买评委的情节。

照你这么说，STOC上的论文都是垃圾？

[big5]

照你这么说，STOC上的论文都是垃圾？

学术圈三五年都不一定能出一篇breakthrough的文章
其他时间不管顶刊顶会，都是在“茴”字有几种写法里打转

[harubashi]

照你这么说，STOC上的论文都是垃圾？

３０年前还有点意思，现在是没问题了硬凸，撸管撸到死

[harubashi]

学术圈三五年都不一定能出一篇breakthrough的文章
其他时间不管顶刊顶会，都是在“茴”字有几种写法里打转

再一看转这条的楼主，哈哈哈，なるほど

[Terminus]

segmented heap, 相当于win10和力扣水平，吨吨吨

[TestCases]

清华在投机取巧上是国内一流的，这个结果就像当年mit的卡他逼那篇faster than FFT一样，一惊一乍吸眼球，其实屁都不是。

大O的上界换了个表达式。这种新的表达式在m (图的边的数量）和n（图的点的数量）相比较， m远低于n^2的情况下，比传统的大O表达式是一个更低的上界. 所以正如文章摘要里说的，这个算法高效的前提是，图必须是稀疏图。

大多数现实世界里提取出来的图都是稀疏图。

我觉得在应用上有潜力。特别是用在那种大的稀疏图上。

[DongshanGe]

这个算法不错
不过老板是第一作者？？？
吨吨吨

中国老师都会抢学生一作，因为坪职称时候，会数一作。

[sgisp2]

中国老师都会抢学生一作，因为坪职称时候，会数一作。

说明你愚蠢！对于导师，一作和通讯作者是一样的作用，除非80%的也是导师做的，可以要两者

[foofy]

再一看转这条的楼主，哈哈哈，なるほど

倭杂反华是常态。

[harubashi]

倭杂反华是常态。

蠢坏怂贱，in the genes of 自干五

[DickIvanka]

突破了一个沉睡了差不多一个世纪的算法。 很牛B。
应该能得图灵奖吧，拭目以待

这种垃圾灌水文 小抠小闹 就是scam， 文章离图灵奖10万八千里

STOC以前还行， 现在就是在钻老鼠洞，钻牛角尖