🚨 经过41年的努力——Dijkstra不再是无敌的。 清华大学、斯坦福大学和信息学MPI的团队实现了第一个确定性算法，打破了有向图中单源最短路径的O(m + n log n)界限，权重为真实非负数。 💡 新运行时间：O(m log^(2/3) n) 📜 旧最佳：Dijkstra + 斐波那契堆 = O(m + n log n) 关键是什么？结合了Dijkstra的“前沿”思想和Bellman-Ford的松弛方法，采用递归前沿划分技巧，使堆保持微小——避开经典的排序障碍。 影响： ⚡ 更快的GPS重新计算 🚦 更顺畅的交通流 📦 更便宜的快递 🌐 更快速的网络路由 📚 是时候重写SSSP算法章节了 自1984年以来，有向SSSP的首次真正加速——而且是确定性的。