败犬日报 2025-08-11

1. 清华段然团队新算法超越 Dijkstra 算法

复杂度 $O (m \log^{2 / 3} n)$ （n 是图的点数，m 是边数），有向图突破了现有的下界（无向图已有 $O (m \sqrt{n \log n \log \log n})$ 的算法）。

Dijkstra 用松驰堆或斐波那契堆的复杂度是 $O (m + n \log n)$ 。Dijkstra 的复杂度实际上是 m 点建堆 + m 次 decrease-key + n 次 extract，所以完全取决于优先队列的实现方式。

适用于稀疏图，因为当 m 近似于 $n^{2}$ 时，新算法变为 $O (n^{2} \log^{2 / 3} n)$ 劣于 Dijkstra。

另外之前的论文证明了 Dijkstra 的普遍最优，但解决的问题是另一个（不是最短路径问题，是顶点的最短路径排序问题）。