Dijkstra 算法杂记

Dijkstra 算法是一种求单源最短路的算法。
使用贪心的思想。

步骤

1. 起始点置 $0$;
2. 找未标记点中 dis 值最小的点;
3. 对该点所有边进行松弛;
4. 标记已访问过该点;
5. 重复 2 到 4 步，直到无法操作。

注意事项

• 在最开始时，dis 值最小的点实际上就是起始点。
• 有负边的情况下不能用 Dijkstra。
• 松弛操作实际上是运用了 $x + a > x$ $(a>0)$ 的原理，即最小路径已然确定，不会因为另一条边而变得更短。
  • 如何证明？
    在没有负环的前提下，已知松弛后 $(u,v)$ 是最短边即最短路径。
    现在假设有其他路径 $(u,w), (w,v)$ 是更短的路径，
    则边 $(u,w)$ 应该在松弛时被认为是最短边，
    但在松弛操作中可以认为 $s_{u,v} < s_{u,w}$，
    则二者矛盾。
    所以松弛筛出的最短边即是最短路径的一部分。

优化

优化前暴力算法复杂度 $O(n^2)$。

使用小根堆（优先队列）$\text{priority queue}$ 进行优化，队列中存储点及其 $dis$ 值。
这样，从队首取出的就是 $dis$ 最小的点，此时遍历这个点的边即可。
复杂度 $O(m\log m)$。

关联板子题

洛谷 P3371 - 单源最短路（弱化版）
洛谷 P4779 - 单源最短路（强化版）