本科必学Dijkstra算法被超越！清华段然团队打破图灵奖得主证明的普遍最优性

主要观点总结

本文报道了清华大学段然团队在最短路径问题算法上的新突破。该新算法改进了图灵奖得主Tarjan提出的O(m + nlogn)算法，运行速度快于任何Dijkstra及其改进算法，并解决了困扰研究人员四十多年的“排序障碍”问题。该算法的应用范围广泛，包括地图APP、计算机网络中的路由协议等。该研究的团队成员包括段然、毛啸等，论文已在理论计算机国际顶级会议STOC 2025上获得最佳论文奖。

关键观点总结

关键观点1: 算法突破

新算法改进了Tarjan的O(m + nlogn)算法，解决了排序障碍问题，运行速度快于任何Dijkstra及其改进算法。

关键观点2: 研究团队成员

研究团队包括清华大学段然、姚班本科毕业生束欣凯、交叉信息院博士生毛嘉怡和尹龙晖等。

关键观点3: 研究影响

该算法解决了一个标志性问题，其进展引发了关注，被认为是一个重要的里程碑。图灵奖得主普林斯顿大学Tarjan教授也表示乐观。