最短路

最短路分为两种：

求每对节点之间的最短路（全源最短路）
求从一个节点出发，到其他节点的最短路（单源最短路）

算法	最短路类型	适用于	时间复杂度（ $n$ 个节点 $m$ 条边）
Floyd	全源最短路	无负环	$O(n^3)$
Bellman-Ford / SPFA	单源最短路	任意图	$O(mn)$
Dijkstra	单源最短路	非负权图	$O(m\log n)$
Johnson	全源最短路	任意图	$\approx$ 跑 $n$ 遍 Dijkstra，即 $O(mn\log n)$

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

该如何选择算法？

非负权图，单源最短路 $\to$ Dijkstra
负权图，单源最短路 $\to$ SPFA
全源最短路 $\to$ Johnson

此外，

求负环 $\to$ SPFA

Floyd

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

Bellman-Ford² 是一种基于“松弛”的算法。设源节点为 $s$ ，我们认为节点 $v$ 到 $s$ 的最短路长度为 $\text{dis}_v$ 。那么松弛的意思是：当我们遍历到一条边 $(u,v)$ 时，执行以下操作：

\text{dis}_v\gets\min\{\text{dis}_v,\text{dis}_u+w(u,v)\}.

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

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

/* Bellman-Ford */
vector<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 (!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$ 没有访问过：
  - 把 $v$ 加入队列。
  - 令 vis[v] = true。

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

Dijkstra

Dijikstra³ 是一种经典的、基于 BFS 的单源最短路算法。

注意

本小节内 Dijkstra 的解释可能和多数参考资料略有不同（但是本质逻辑是一样的）。

下面假设源节点为 $s$ 。Dijkstra 的算法过程需要维护三个集合：

已经确定到 $s$ 的最短路长度的点集 $S$ ，初始化为 $\{s\}.$
未能确定到 $s$ 的最短路长度的点集 $T$ ，初始化为 $G\setminus\{s\}.$
一个候选点集 $C$ ，初始化为 $\varnothing$ （C = candidate）。

此外，我们还要对每个节点维护其到 $s$ 的最短路长度 $\text{dis}_u$ 。 $\text{dis}_s$ 初始化为 $0$ ，其他节点初始化为 $+\infty$ 。

重复以下过程

我们从 $S$ 中取出一个节点，记为 $u$ ，

把 $u$ 所有出边连接的节点移入 $C$ ，并把 $C$ 中所有节点用 $u$ 松弛。即对 $C$ 中的每个节点 $p$ ，如果边 $(u,p)$ 存在，执行 $\text{dis}_p\gets\min\{\text{dis}_p,\text{dis}_u+w(w,p)\}$ 。
从 $C$ 中选出 $\text{dis}$ 最小的节点，将其移入 $S$ 。（即对于 $C$ 中 $\text{dis}$ 最小的节点，其最短路长度已经确定了）

当 $T$ 为空时，算法结束。

编码

实际编码时，我们不需要真的实现三个集合 $S,T,C$ 。下面给出一种使用单个优先队列的写法。

在 Dijkstra 的过程中，我们需要不断寻找 $\text{dis}$ 最小的节点。不妨将一个带有 $\text{dis}$ 信息的 Node 结构体入队，则每次取队首的元素就行了。请看下面的代码（“替身”是何意味下文会解释）：

/* Dijkstra 全局定义 */
struct Node {
    int head, dis = 1e9;
    int id; // node[i].id 存的就是 i，之后我们会让 "替身" 入队，而不是本体
            // 故要存下 id 用于寻找本体
    bool operator<(const Node& another) const {
        return dis > another.dis; // 反其道而行之，实现小根堆
    }
} node[MAXN + 1];
bool vis[MAXN + 1]; // vis[i] 用于标记 node[i] 的最短路是否已经确定

我们先要跑一遍 for 初始化 Node::id，然后是算法主体：

/* Dijkstra 主体 */
priority_queue<Node> pq;
node[s].dis = 0;
pq.push(node[s]); // 源节点入队
Node tt;
while (!pq.empty()) {
    tt = pq.top(); pq.pop(); // 取出队首节点
    if (vis[tt.id]) continue; // 如果已经确定最短路，则跳过
    vis[tt.id] = true; // 标记，相当于将 tt 移入 S 集合
    // 遍历 tt 的边
    for (int e = tt.head; e; e = edge[e].next) {
        int v = edge[e].v;
        if (node[v].dis > tt.dis + edge[e].w) {
            // 用 tt 松弛 v
            node[v].dis = tt.dis + edge[e].w;
            // 松弛后让 "替身" 入队
            pq.push(node[v]);
        }
    }
}
// 队列为空，算法结束

现在可以解释为什么要用“替身”入队+ vis 了：

首先考虑：可不可以不让 Node 入队，而是让 id（即节点编号）入队，然后每次取 pq.top() 即得到 $\text{dis}$ 最小的节点？如果如此，每次某节点被松弛后，相当于从“外部”改变了队列中节点的属性，因而接下来队中会处于混乱状态，无法保证取出的节点是 $\text{dis}$ 最小的。只有我们把被松弛的节点从队中“挖出来”再放回去，才能保证队首的 $\text{dis}$ 是最小的。而实际上我们做不到这一点（优先队列不能随机访问）。
于是我们选择每次松弛后将被松弛的节点的“替身”入队。注意这样做之后队中可能会存在同一节点多个“替身”，如何保证正确性？由于新的“替身”刚被松弛，其 $\text{dis}$ 一定比队内之前所有的“替身”更小。因而最终我们一定会先取出同一节点的 $\text{dis}$ 最小的那个“替身”，可以保证正确性。
不难想到 vis 的意义：同一节点，我们只会用它的第一个“替身”，vis 用于避免重复操作某一节点。

时间复杂度

信息

Dijkstra 有几种常见的实现，它们的时间复杂度各不相同。具体可以参考最短路 - OI Wiki # 时间复杂度。下面给出的是上文写法的时间复杂度。

每次松弛的时间复杂度为 $O(\log n)$ ，每条边最多松弛一次，故总复杂度为 $O(m\log n)$ 。

Johnson

朴素的想法就是真的分别以每个节点为源节点，跑 $n$ 遍 Dijkstra，这样的时间复杂度是 $O(mn\log n)$ ，但是不适用于有负权边的情况。

修复

核心思想是：重新标记边的权值，使得所有权值非负，然后跑 $n$ 遍 Dijkstra。具体做法如下：

新建一个虚拟节点，不妨记为节点 $0$ （因为 $99\%$ 的图论题的节点都是从 $1$ 开始编号的）。
从 $0$ 向所有节点连边，这些边的权值都设为 $0$ 。
由于负权值边的存在， $0$ 到某个节点的最短路长度可能小于 $0$ 。于是，我们跑一次 Bellman-Ford 算法，求出 $0$ 到其余所有结点的最短路长度。 $0$ 到 $u$ 的最短路长度就记为 $h_u$ 。时间复杂度为 $O(mn)$ 。
将图中所有边 $(u,v)$ 的权值更新为： $w(u,v)+h_u-h_v$ 。

然后再跑 $n$ 遍 Dijkstra 就好了。总时间复杂度为 $O(mn+mn\log n)=O(mn\log n)$ 。

笔者认识的大多数人读作“弗洛伊德”。 ↩
笔者读作“贝尔曼-福特”。 ↩
笔者读作“迪杰斯特拉”。 ↩

该如何选择算法？​

Floyd​

Bellman-Ford​

SPFA​

Dijkstra​

重复以下过程​

编码​

时间复杂度​

Johnson​

修复​

Footnotes​