【突破40年Dijkstra算法瓶颈，清华教授等颠覆教科书！斩获STOC最佳论文】

1.Dijkstra 算法的局限：1956 年，计算机科学家埃兹赫・迪杰斯特拉（Edsger Dijkstra）提出的 Dijkstra 算法是解决该问题的经典方法。其原理是从起点开始，按距离从近到远的顺序逐步探索节点（先找最近节点，再找次近节点），本质依赖对节点距离的排序。

但这种思路存在 “排序瓶颈”：算法速度无法快于排序所需时间。1984 年，Robert Tarjan 等人改进后，Dijkstra 算法在稀疏图上达到 O (m + n log n) 的时间复杂度（m 为边数，n 为节点数），但此后 40 年，学界始终无法突破这一由排序带来的速度极限，尤其难以扩展到任意权重的有向图（边有单向性，如 A 到 B 易、B 到 A 难的场景）。

2.突破：清华团队新算法打破 “排序瓶颈”

[不愧是你]核心成果
清华大学段然教授团队与合作者提出的新算法，首次在有向图（含非负权重边）的单源最短路径问题（SSSP）中打破排序瓶颈。其时间复杂度为O(m log²/³ n)，显著优于 Dijkstra 算法在稀疏图上的 O (m + n log n)，且不依赖排序，运行速度更快。相关论文《Breaking the Sorting Barrier for Directed Single-Source Shortest Paths》于 2025 年 7 月发表，并获 STOC（理论计算机科学顶级会议）最佳论文。

[点赞]算法创新原理

新算法通过两大核心思路突破瓶颈：
集群分组减少筛选成本：不再严格按距离顺序探索节点，而是将边界节点（已探索区域的相邻节点）分组为集群，每步仅从每个集群中筛选节点，减少需处理的节点数量，规避排序依赖。
分阶段借鉴贝尔曼 - 福特算法：贝尔曼 - 福特算法虽不排序，但原生速度远慢于 Dijkstra。团队通过分阶段运行该算法，定位网络中的 “关键节点”（类似交通枢纽，多数最短路径需经过），优先探索这些节点，再回溯处理其他边界节点，既避免排序，又提升效率。
确定性设计：算法无需依赖随机性（学界更青睐确定性方案），由斯坦福大学博士生毛啸提出关键优化，解决了早期版本的随机化依赖问题。
论文链接：http://t.cn/A6sGSzv4