最短路

最短路分为两种：

• 求每对节点之间的最短路（全源最短路）。

• 求从一个节点出发，到其他节点的最短路（单源最短路）。

算法	最短路类型	适用于	时间复杂度
Floyd	全源最短路	无负环	$O(n^3)$
Bellman–Ford / SPFA	单源最短路	任意图	$O(mn)$
Dijkstra	单源最短路	非负权图	$O((m+n)\log m)$，极致优化可达 $O(m\log m)$
Johnson	全源最短路	任意图	相当于跑 $n$ 遍 Dijkstra，优化拉满 $O(mn\log m)$

注意：$u\to v$ 的最短路存在，当且仅当 $u\to v$ 的所有路径不经过负环。

Floyd

这其实是一种 DP 算法：定义 $f[k][x][y]$ 表示：允许通过节点 $[1,k]$，$x\to y$ 的最短路径。

那么我们的转移方程就是：$f[k][x][y]=\min\{f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]\}$。

考虑边界情况：

• 如果 $x\to y$ 之间有一条边，$f[0][x][y]$ 就是这条边的边权。

• 如果 $x\to y$ 之间没有边，令 $f[0][x][y]=+\infin$。

容易想到，$f$ 的第一位是可以用滚动数组优化掉的。显然时间复杂度是 $O(n^3)$。

Floyd 还可以解决：最小环、传递闭包（判断任意两点是否连通）问题。

Bellman-Ford

这是一种基于 “松弛” 的算法。松弛的意思是：假设我们认为 $s\to v$ 的最短路径长度为 $\text{dis}(s,v)$，其中 $s$ 就是 “单源最短路” 的 “源”，我们现在尝试这样更新它：

$$[\text{dis}(s,v)]^\prime=\min\{\text{dis}(s,v),\text{dis}(s,u)+w(u,v)\}.$$

其中 $w(u,v)$ 就是边 $(u,v)$ 的边权。这时，我们就说节点 $u$ 参与了松弛。

那么最多会松弛多少次呢？每次松弛最多会使得（我们认为的） $s\to v$ 的最短路多经过一条边，而我们一共有 $m$ 条边，所以最多松弛 $mn$ 次，时间复杂度就是 $O(mn)$。所以我们这样写代码：

int dis[n+1]; // dis[i] 表示 s->i 的最短路长度（我们认为的）
for (int i = 1; i <= n) dis[n] = INT_MAX; // 初始化为 +inf
bool flag; // 记录我们有没有松弛
for (int i = 1; i <= n; i++) {
    flag = false;
    for (int j = 1; j <= m; j++) {
        Edge e = edges[i];
        if (dis[e.from] == INT_MAX) continue; // 我们还没连到这条边呢
        if (dis[e.to] > dis[e.from] + dis[e.w]) {
            dis[e.to] = dis[e.from] + dis[e.w];
            flag = true;
        }
    }
    if (not flag) break;
}
if (flag) throw "有负环！";

注意：这里只能判断从 $s$ 出发可以到达的路径上有无负环。

SPFA

SPFA 是对 Bellman-Ford 一定程度上的优化，但其最坏时间复杂度仍为 $O(mn)$。

在 Bellman-Ford 中，我们枚举了很多不需要松弛的边，如何优化？我们发现：只有上一次参与松弛的节点，其连接的边才有可能触发下一次松弛。

这样为什么成立我没想明白。

所以我们这样实现：

• 维护一个 vis[] 数组。vis[i] 维护的是：节点 $i$ 是否因为参与松弛而添加到队列。这样可以防止重复入队的情况。

• 把 $s$ 添加到队尾并令 vis[s] = true。

• 循环以下步骤，直到队列为空：

  • 取出队首元素，记为 $u$。令 vis[u] = false。

  • 遍历从 $u$ 出发的每条边。假设有一条边 $(u,v)$，尝试用 $\text{dis}(s,u)+w(u,v)$ 松弛 $\text{dis}(s,v)$。

  • 如果 $v$ 没有访问过：

    • 把 $v$ 加入队列。

    • 令 vis[v] = true。

用 SPFA 判断有无负环的方法略有不同，详见：最短路 - OI Wiki。

Dijkstra

经典的算法，是一种 BFS。