最短路

Bellman-Ford

这是一种暴力求解单源最短路的方法。如果图不存在负环，那么任意两点之间的最短路一定不经过相同的点。

假设 \(A\) 到 \(E\) 的最短路径为 \(A \to B \to C \to D \to E\)，那么 \(A \to B \to C \to D\) 一定为 \(A\) 到 \(C\) 的最短路。

记 \(dis_{x}\) 表示起点 \(s\) 到 \(x\) 的最短路长度。假设当前已经有经过点数为 \(i\) 的最短路，那么对每条边 \(u \to v\) 都进行（记为松弛）：\(dis_{v} = \min(dis_{v},dis_{u}+w)\) 的操作（初始 \(dis_{s}=0\)，其余点 \(dis\) 为 \(+\infty\)）。这样一定能得到点数为 \(i+1\) 的最短路。进行 \(n-1\) 次松弛就能算出最短路了。

如果在进行第 \(n\) 次松弛时，还有点的 \(dis\) 值在变小，说明存在经过点数大于 \(n\) 的最短路，即整个图存在负环。

这种算法的时间复杂度为 \(O(nm)\)。

SPFA

容易发现在 Bellman-Ford 中，存在许多无效的松弛，对于边 \(u \to v\)，当 \(dis_{u}\) 从未被更新过或者 \(u \to v\) 进行过一次松弛后，\(dis_{u}\) 再也没被更新过，称此时进行的 \(u \to v\) 的是 \(No\) 的，否则称其是 \(Yes\) 的。

尝试去掉这样的无效松弛。维护一个队列，里面的点 \(u\) 进行的扩展（扩展指对一个 \(u\) 而言，\(u \to v\) 的所有松弛）是 \(Yes\) 的。每次取出队头 \(u\) 进行扩展，把更新成功且此时不在队列里的点 \(v\) 放进队列里。然后弹出 \(u\)。

当队列为空时，说明所有 \(u \to v\) 的松弛全是 \(No\) 了，此时 \(dis_{i}\) 即为正确最短路。

如果存在负环，那么队列将一直非空。这样的情况该怎么判断呢？记 \(Len_{i}\) 表示当前 \(s\) 到 \(i\) 的最短路经过的点数。如果松弛时存在一个点的 \(Len_{i}\) 大于 \(n\)，就说明存在负环。

在一般图上速度很快，但能被卡成 \(O(nm)\)。

Dijkstra

Dijkstra 算法适用于非负权图。直接介绍这个算法的过程和证明吧。

过程：将节点分成两个集合 \(S\) 和 \(T\)，\(S\) 表示已确定最短路的点集（即 \(dis_{i}\) 一定正确的点），\(T\) 表示 \(dis_{i}\) 不一定正确的点集。每次在 \(T\) 中选出一个最小的 \(dis\) 值的点，把该点放入 \(S\) 里，然后进行对它一次扩展。直到所有点都在 \(S\) 里。最开始把所有点放入 \(T\) 里，\(dis_{s}=0\)，其余点 \(dis\) 为 \(+\infty\)。

用堆来实现，记 \(vis_{i}\) 表示 \(i\) 是否在 \(S\) 里，每次取出堆顶 \(x\)，如果 \(vis_{x}\) 为 \(0\)，对 \(x\) 做一遍扩展，如果 \(dis_{y}\) 成功更新就加入堆里。然后弹出 \(x\)。用 \(vis\) 的原因是同一个点会 \(x\) 多次入堆，但是第一次取出时才进行扩展。

由于每个点只可能进行一次扩展，总共最多会松弛 \(m\) 次，堆的大小最多达到 \(m\)，所以该算法时间复杂度为 \(O(m \log m)\)。当图为稠密图时，直接暴力更优，时间复杂度为 \(O(n^2)\)。

证明：这个算法是正确的当且仅当每次 \(T\) 中取出的最小 \(dis\) 值一定是正确的。归纳假设 \(S\) 里的 \(p_{1},p_{2},\dots,p_{k-1}\) 里的 \(dis\) 一定是正确的。记 \(p_{k}\) 为在 \(T\) 中 \(dis\) 最小的点。如果存在一条经过了 \(T\) 中的点的路径的长度比 \(S\) 扩展而来的 \(dis_{p_{k}}\) 更小。

即 \(dis_{A} \le dis(p_{i})+w(p_{i},A)+w(B,C)+\dots+w(D,p_{k})<dis_{p_{k}}\)，所以 \(dis_{A} < dis_{p_{k}}\)，与 \(dis_{p_{k}}\) 在 \(T\) 中最小矛盾。故而从 \(S\) 中扩展而来的最小的 \(dis_{p_{k}}\) 的值一定是正确的。算法成立。