最短路是图论最基本的一类问题。

下文记 \(dis_u\) 表示从源点到节点 \(u\) 的最短路，\(n\) 为节点数 \(|V|\)，\(m\) 为边数 \(|E|\)。

Bellman-Ford 是一种非常暴力的求解最短路的方法（BF 之于 dijkstra 如同 FF 之于 dinic）。

称一轮 松弛 为对于每一条边 \((u, v)\)，用 \(dis_u + w_{u, v}\) 更新 \(dis_v\)。我们断言每轮至少有一个节点的最短路被更新，松弛 \(n - 1\) 轮即可。

正确性证明：设源点为 \(1\)。在 \(1\to u\) 的最短路 \(1\to p_1\to\cdots\to u\) 中，对于每个节点 \(p_i\)，\(1\to p_1\to\cdots\to p_i\) 也一定是 \(1\to p_i\) 的最短路，反证法易证。所以一个节点的最短路一定由另一个节点的最短路扩展而来。因为最短路最多有 \(n - 1\) 条边，而第 \(i\) 轮松弛会得到边数为 \(i\) 的最短路，故至多只需松弛 \(n - 1\) 轮。

该算法还可以判断一张图上是否存在负环。如果在第 \(n\) 轮松弛时仍有节点的最短路被更新，那么图存在负环。

算法的时间复杂度为 \(\mathcal{O}(nm)\)。

dijkstra 是基于 贪心 的最短路算法，适用于 非负权图。

称 扩展 节点 \(u\) 为对于 \(u\) 的所有出边 \((u, v)\)，用 \(dis_u + w_{u, v}\) 更新 \(dis_v\)。

在已经得到最短路的节点中，取出没有扩展过的距离源点最近（即 \(dis\) 最小）的节点并扩展。因为没有负权边，所以取出的节点的最短路长度单调不降。

如何判断一个节点已经取到了最短路？实际上不需要判断，每次取出的节点恰取到了其最短路。根据边权非负以及 dijkstra 的贪心算法流程，可以通过归纳法与反证法证明这一点。

归纳假设已经扩展过的节点 \(p_1, p_2, \cdots, p_{k - 1}\) 在扩展时均取到了其最短路。\(p_k\) 为没有被扩展的 \(dis\) 最小的节点。

\(p_k\) 的最短路一定由 \(p_i(1\leq i < k)\) 的最短路扩展而来，不可能出现 \(dis(p_i) + w(p_i, p_{k + 1}) + w(p_{k + 1}, p_k) < dis(p_j) + w(p_j, p_k)(1\leq i, j < k)\) 的情况。否则由于边权非负，\(w(p_{k + 1}, p_k) \geq 0\)，所以 \(dis(p_i) + w(p_i, p_{k + 1}) < dis(p_j) + w(p_j, p_k)\)，即当前 \(dis(p_{k + 1}) < dis(p_k)\)，与 \(dis(p_k)\) 的最小性矛盾。

初始令源点的 \(dis\) 为 \(0\)，假设成立，因此算法正确。

取出 \(dis\) 最小的节点的过程可以用优先队列 priority_queue 维护。每次扩展 \(u\) 时，若 \(dis_u + w_{u, v} < dis_v\)，那么将 \((v, dis_u + w_{u, v})\) 即节点编号和它更新后的 \(dis\) 作为二元组丢进优先队列。尝试取出节点时，以 \(dis_u + w_{u, v}\) 为关键字取出最小的二元组，则它对应的节点编号就是我们要找的节点。

注意，一个节点可能有多个入边并多次进入优先队列。但当它第一次被取出时，得到的一定是最短路。为此，需要记录 vis[i] 表示一个节点是否被扩展过。若当前取出节点已经被扩展过，则忽略。也可以判断是否有当前二元组的第二个元等于第一个元（节点编号）的 \(dis\)，若不等说明当前节点被扩展过了。否则复杂度将退化为 \(m ^ 2\log m\)。

算法的时间复杂度为 \(\mathcal{O}(m\log m)\)。

P4779 模板题代码。

Johnson 算法用于解决 带有负权边 的 全源最短路经 问题。所谓全源最短路径问题，就是求解图上任意两个点之间的最短路。

Johnson 算法的巧妙之处在于为每个点赋予 势能 \(h_i\)。正如物理意义上的势能，从一个点出发，到达另一个点，无论走什么路径，势能的总变化量是一定的。物理实际启发我们将边 \((u, v)\) 的新权值 \(w'_{u, v}\) 设置为 \(w_{u, v} + h_u - h_v\)。

考虑一条路径 \(S\to p_1 \to p_2 \to \cdots \to T\)，其原长为

新的长度为

化简后不难看出 \(L(S\to T) = L'(S\to T) + h_T - h_S\)。对于固定的 \(S, T\)，原图的路径对应到新图上面，长度增加了 \(h_S - h_T\)。这与路径经过了哪些节点无关，而只与 \(S, T\) 有关。因此，原图上 \(S\to T\) 的最短路在新图上 仍为最短路。

接下来考虑求解原问题。

由于负权，我们无法使用 dijkstra 求解最短路。多次 SPFA 或 BF 的时间复杂度不优秀。尝试应用上述分析，合理地为每个点赋权值，从而消去图上的所有负权边。

为使 \(w'(u, v) \geq 0\)，只需 \(w(u, v) + h_u \geq h_v\)。这是什么？三角形不等式！若初始图中无负环，那么我们一定可以不断松弛最终得到这样一个 \(h\)。具体地，初始令所有 \(h\) 等于 \(0\)，然后使用 BF 算法进行 \(n - 1\) 轮松弛。

松弛在 \(n - 1\) 轮后必然结束，否则意味着原图存在负环，因为上述操作等价于建立虚点 \(0\) 并向所有节点连一条边权为 \(0\) 的边，并求出 \(0\to i\) 的最短路 \(h_i\)。

操作结束后，我们更新每条边的权值 \(w'(u, v) = w(u, v) + h(u) - h(v)\)。根据一开始的分析，得到的新图与原图任意两点间的最短路径不变，且 没有负边权，可以使用 \(n\) 轮 ijkstra 求解任意两点间的最短路。

最后不要忘了 将 \(u\to v\) 的最短路加上 \(h_v - h_u\)。

算法的时间复杂度为 \(\mathcal{O}(nm\log m)\)。

模板题 P5905 代码。