最短路

Floyd 全源最短路

设 $f_{t,u,v}$ 为只经过图中 $[1,t]\cup\{u,v\}$ 中的点，$u\to v$ 的最短路。$f_{0,u,v}$ 即 $u$ 到 $v$ 的所有边中的边权最小值，$u$ 到 $v$ 间无边即为 $+\infty$。

那么转移为 $f_{t,u,v}\xleftarrow[k]{\min}f_{t-1,u,k}+f_{t-1,k,v}$。复杂度 $O(n^3)$

Bellman-Ford 单源最短路

维护 $d_u$，第 $t$ 轮更新时表示从起点到点 $u$ 经过不超过 $t$ 条路径的最短路。

每轮更新时遍历每条边 $(u,v,w)$，令 $d_v\xleftarrow[]{\min}d_u+w$。

这样做的正确性是显然的，考虑到若原图存在最短路，那么起点到每个点一定存在一条长度不超过 $n-1$ 的最短路。所以在经历 $n-1$ 轮更新后 $d_i$ 即为起点到 $i$ 的最短路；也即如果第 $n$ 轮更新仍然有 $d$ 变小，说明原图不存在最短路，即存在负环。

时间复杂度 $O(nm)$。

SPFA 单源最短路

Bellman-Ford 中每轮更新会遍历一遍所有点。实际上只有上一轮中 $d$ 减小的那些点有更新其它点的能力。所以我们维护一个队列，每次取队头出来更新其它点。

显然一个点 $u$ 第 $t$ 次入队时，$d_u$ 一定小于等于 Bellman-Ford 中第 $t$ 轮更新后 $d_u$ 的值。那么一个点入队 $n$ 次说明原图存在负环。

时间复杂度 $O(nm)$。

Dijkstra 单源最短路

对于一个无负权边的图，维护一个集合 $S$ 包含所有已经求得最短路的点。初始为空集。

再维护 $d_i$ 表示用 $S$ 中的点能够更新得的每个点最短路，特殊地，起点的 $d$ 值为 $0$。

每轮更新时，考察不在 $S$ 中的所有点中 $d$ 最小者 $i$，由于在 $S$ 中的点已经更新过了，不在 $S$ 中的点已经无法再更新它，所以此时 $d_i$ 即为 $i$ 的最短路。将其加入 $S$ 并更新其它所有点。

找出不在 $S$ 中的所有点中 $d$ 最小值这一步，暴力求得时间复杂度为 $O(n^2)$，使用不支持删除的堆（priority_queue）为 $O(m\log m)$，使用支持删除的堆为 $O(m\log n)$，使用支持 $O(1)$ 插入的堆（斐波那契堆、配对堆等）为 $O(n\log n+m)$。

Johnson 全源最短路

对于无负权边的图，全源最短路可以对每个点都做一遍 Dijkstra，时间复杂度为 $O(nF(n,m))$，其中 $F(n,m)$ 为一轮 Dijkstra 的时间复杂度，若使用堆实现，其时间复杂度低于 Floyd 的 $O(n^3)$。

对于一般图没办法直接应用 Dijkstra。我们尝试给每个点 $t$ 都规定一个权值 $h_t$，并将每条边 $(u,v,w)$ 边权改为 $w+h_u-h_v$。不难发现，无论 $h$ 取什么值，新图最短路即原图最短路，且新图上 $s\to t$ 的最短路长度为原图上 $s\to t$ 的最短路长度加上 $h_s-h_t$。

为了使新图能够应用 Dijkstra，我们需要求出一组合适的 $h$ 使新图上没有负权边。即对于每条边 $(u,v,w)$ 有 $w+h_u-h_v\ge0$。于是变成了一个差分约束问题。先做一遍 SPFA 得到 $h$，修改边权，然后以每个点为起点分别做一遍 Dijkstra，最后求得原图上最短路即可。