最短路学习笔记

单源最短路径问题（Single Source Shortest Path，SSSP问题）。

Part1 Dijkstra

Part1.0 Dijkstra 朴素算法

洛谷 P3371 【模板】单源最短路径（弱化版）

Dijkstra 算法

Dijkstra 算法的流程如下：

1. 初始化 $dist[1]=0$，其余节点的 $dist$ 值为正无穷大。
2. 找出一个未被标记的、 $dist[x]$ 的最小节点 $x$，然后标记节点$x$。
3. 扫描节点 $x$ 的所有出边 $(x,y,z)$，若 $dist[y]>dist[x]+z$，则使用 $dist[x]+z$ 更新 $dist[y]$。
4. 重复上述 2~3 两个步骤，知道所有节点都被标记。

Dijkstra 算法基于贪心思想，它只适用于所有边的长度都是非负数的图。Dijkstra 算法的时间复杂度为 $\mathcal{O}(n^2)$。

Part1.1 Dijkstra 堆优化

观察 Dijkstra 的流程，我们发现步骤2可以优化。

我们可以用堆对 $dist$ 数组进行维护，用 $\mathcal{O}(\log n)$ 的时间取出堆顶元素并删除，用 $\mathcal{O}(\log n)$ 的时间遍历每条边，总时间复杂度为 $\mathcal{O}((n+m) \log n)$。

Part2 Bellman-Ford & SPFA

Part2.0 Bellman-Ford算法

将所有边进行 $n-1$ 次松弛操作，在求解它的过程中，每次循环都要修改所有顶点对应的 $dist$ 数组的值，最短路径长度直到算法结束才能确定。算法的时间复杂度为：$\mathcal{O}(nm)$。

Part2.1 SPFA算法

SPFA 算法，即 Shortest Path Faster Algorithm，最短路径快速算法。

SPFA 算法在 Bellman-Ford 算法上进行了优化，将待更新的 $dist$ 数组的对应顶点存进队列里，每次取出队首元素 $u$，将与 $u$ 相连的节点进行松弛，如果节点 $y$ 不在队列里，且 $dis[y]$ 可以更新，那么将节点 $y$ 入队。

与 BFS 不同的是，SPFA 算法可以将一个节点多次入队。

SPFA 算法的时间复杂度为 $\mathcal{O}(km)$ ，其中 $k$ 是一个较小的常数。但是，如果题目数据故意卡 SPFA ，那么 SPFA 的时间复杂度会退化为 $\mathcal{O}(km)$。相较于 SPFA，Dijkstra 算法更为稳定。