报告题目：更快的单源最短路算法

主讲人：段然 副教授

时  间： 2026年5月21日（周四）下午15:30-16:30

地  点：腾讯会议（会议号：319-172-481）

主办单位：科技处

承办单位：人工智能学院

主讲人介绍：

段然，清华大学交叉信息研究院副教授。本科毕业于清华大学计算机系，2011年获密歇根大学计算机系博士学位，导师为 Prof. Seth Pettie，方向为理论计算机科学。此后在德国马克斯普朗克信息学研究所任博士后研究员，并获得洪堡奖学金。2014年8月加入清华大学交叉信息研究院。主要研究方向为图论算法、数据结构、计算理论等，在理论计算机领域顶级会议 STOC、FOCS、SODA、ICALP 发表论文29篇，成果涵盖最大匹配、矩阵乘法和最短路等基础问题的突破性进展。

报告摘要：

主要介绍最新的无向图和有向图单源最短路（SSSP）算法，包括时间复杂度为 O(m \log^{1/2+o(1)} n) 的无向图 SSSP 随机算法（Duan, Mao, Shu, Yin, FOCS 2023），以及时间复杂度为 O(m \log^{2/3} n) 的有向图 SSSP 确定性算法（Duan, Mao, Mao, Shu, Yin, STOC 2025）。该系列成果打破了 Dijkstra 算法的排序时限，表明最短路算法并不一定需要对所有点排序。

欢迎全校教师线上参会交流。