清华大学交叉信息研究院段然团队获得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
-
南宁左江会展商务服务有限公司 18067

-
上海创蓝文化传播有限公司 8062

-
中国粮油学会玉米深加工分会 21185

-
江西九江城际会议服务有限公司 18262

-
中汇(广州)国际会展有限公司 8754

-
武汉致远会务 18172

-
天津市硅酸盐学会 8123

-
中国石油和化学工业协会培训中心 2124

-
中国林业科学研究院热带林业研究所 23208

-
东北大学 8128

-
深圳国泰安教育技术有限公司 8158

-
武汉海讯科技会务有限公司 25228

-
赛特数码有限公司 18076

-
北京国宏信科信息技术研究院有限公 18125

-
同济大学MBA中心 21267

-
中国科学院电工研究所 23057

-
第四军医大学西京医院放疗科 18303

-
WILL 24080

-
上海信世展览服务有限公司 2047

-
海南优为会务 18464

















344










































