40年后，Dijkstra算法极限再被突破，清华段然团队更快最短路径算法摘STOC最佳论文

清华交叉信息研究院段然团队提出了一种突破性的最短路径算法，首次在有向图中打破了经典的 Dijkstra 算法在稀疏图上的 O(m + n log n) 时间复杂度下界。该算法基于分层递归和前沿缩减策略，结合 Bellman-Ford 的思想，避免了传统算法中必须的排序操作，将时间复杂度降至 O(m log²/³n)。该成果发表于理论计算机顶级会议 STOC 2025，并荣获最佳论文奖。这一进展为高效路径计算提供了新思路，尤其适用于只需输出距离而不要求排序的场景。
来源：https://mp.weixin.qq.com/s/C6UZcmkQThZXbNYgCGKkLA