Dijkstra

算法步骤

• 将d和vis数组初始化为 \(+\infty\)，d[s] = 0；
• 遍历所有vis = 0的点，找到d最小的一个点，标记vis = 1；
• 通过该点的所有出边松弛其它点；
• 若存在节点vis = 0，重复2、3步骤。

朴素 Dijkstra

Step 2：单次 \(O(n)\)，均摊 \(O(n^2)\) ； Step 3：单次 \(O(n)\)，均摊 \(O(m)\)。 总时间复杂度 \(O(n^2+m)\) 。

堆优化 Dijkstra

Step 2：单次 \(O(\log m)\)（堆中最多有 m 个元素），均摊 \(O(n \log m)\) ； Step 3：单次 \(O(n \log m)\)，均摊 \(O(m \log m)\)。 总时间复杂度 \(O((n+m) \log m)\) 。

对比

堆优化 Dijkstra 适用于较为稀疏的图，因为 \(m \ll n^2\)，\(n+m\) 较小。

朴素 Dijkstra 适用于稠密图，因为 \(m\) 和 \(n^2\) 在同一量级，时间复杂度为 \(O(n^2)\)；这时堆优化会退化为 \(O(n^2\log n)\)。