清华大学交叉信息研究院段然团队获得STOC 2025论文奖
2025/05/17
近日,清华大学交叉信息院段然团队的论文“突破有向单源最短路径的排序障碍”(Breaking the Sorting Barrier for Directed Single-Source Shortest Paths)在理论计算机国际顶级会议STOC 2025(ACM SIGACT Symposium on Theory of Computing,ACM理论计算特别兴趣小组理论计算研讨会)上获得最佳论文奖。
段然团队探讨了图论算法中经典的“单源最短路径问题(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级博士生毛啸也作出了贡献。
文章来源清华大学,分享只为学术交流,如涉及侵权问题请联系我们,我们将及时修改或删除。
-
2026年1月高含金量国际学术会议合 12-12
-
第四届金融科技与商业分析国际学术会议 686
-
2026年第十一届复合材料与材料工程 1453
-
2025年机器视觉、智能成像与模式识 2126
-
2025年智能光子学与应用技术国际学 3284
-
2026年机械工程,新能源与电气技术 3476
-
2025年计算机科学、图像分析与信号 3917
-
2025年材料化学与燃料电池技术国际 3633
-
2026年交通数字化、人工智能与韧性 12-19
-
2026年社会文化与公共管理国际会议 12-19
-
2026年人文地理与语言研究国际会议 12-19
-
2026年社会发展与经济发展国际会议 12-19
-
2026年光伏材料、光电转换与可再生 12-19
-
2026年可持续发展与数字化社会国际 12-19
-
2026年管理科学、语言与教育国际会 12-19
-
2025年两院院士增选有效候选人2672
-
2025最新JCR分区及影响因子7552
-
好学术:科研网址导航|学术头条分3540
-
2025年国际期刊预警名单发布!3510
-
2025年中科院期刊分区表重磅发13412
-
中国科协《重要学术会议目录(207866
-
吉林大学校长张希:学术会议中的提4517
-
中国科大提出电化学一体化驱动策12-19
-
中国科大实现电泵浦片上集成高亮度12-19
-
西北农林科技大学【陕西新闻联播】12-19
-
中国科大实现片上非相干泵浦高品质12-19
-
中国科大中性原子量子计算研究成果12-19
-
炔烃远端C-O键的不对称活化转化12-19
-
研究揭示叶片内生真菌分子功能多样12-19
-
科研人员提出柑橘黄龙病防控新策略12-19
-
苏州工业园区纳米技术产业创新中心 24108

-
纳通医疗集团 18284

-
hksme 23177

-
北京邮电会议中心 23206

-
吉林省北华大学师范分院美术系 21119

-
第五届中国民营经济高峰会 18063

-
宁波雅卓展览服务有限公司 24198

-
星河系教育 2121

-
上海浦东盛高假日酒店 2136

-
国际工学技术出版协会 23025

-
IETP 2125

-
西安纳米科技学会 8388

-
国际工学技术出版协会 2044

-
中国科学院计算技术研究所 23108

-
MHGXMHF 8250

-
中国金属学会 23104

-
华中科技大学同济医学院附属同济医 21293

-
河北省黄骅市绿园化工有限公司 18039

-
中国土木工程学会港口工程分会 18314

-
上海翊驰投资发展有限公司 8203

















346










































