最短路
定义
（还记得这些定义吗？在阅读下列内容之前，请务必了解 图论相关概念 中的基础部分。）
- 路径
- 最短路
- 有向图中的最短路、无向图中的最短路
- 单源最短路、每对结点之间的最短路
记号
为了方便叙述，这里先给出下文将会用到的一些记号的含义。
为图上点的数目， 为图上边的数目； 为最短路的源点； 为 点到 点的 实际 最短路长度； 为 点到 点的 估计 最短路长度。任何时候都有 。特别地，当最短路算法终止时，应有 。 为 这一条边的边权。
性质
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。
对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过
Floyd 算法
是用来求任意两个结点之间的最短路的。
复杂度比较高，但是常数小，容易实现（只有三个 for）。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
实现
我们定义一个数组 f[k][x][y]，表示只允许经过结点
很显然，f[n][x][y] 就是结点
接下来考虑如何求出 f 数组的值。
f[0][x][y]：f[0][x][y] 什么时候应该是
f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])（f[k-1][x][y]，为不经过 f[k-1][x][k]+f[k-1][k][y]，为经过了
上面两行都显然是对的，所以说这个做法空间是
因为第一维对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。
证明第一维对结果无影响
对于给定的 k，当更新 f[k][x][y] 时，涉及的元素总是来自 f[k-1] 数组的第 k 行和第 k 列。然后我们可以发现，对于给定的 k，当更新 f[k][k][y] 或 f[k][x][k]，总是不会发生数值更新，因为按照公式 f[k][k][y] = min(f[k-1][k][y], f[k-1][k][k]+f[k-1][k][y]),f[k-1][k][k] 为 0，因此这个值总是 f[k-1][k][y]，对于 f[k][x][k] 的证明类似。
因此，如果省略第一维，在给定的 k 下，每个元素的更新中使用到的元素都没有在这次迭代中更新，因此第一维的省略并不会影响结果。
综上时间复杂度是
应用
给一个正权无向图，找一个最小权值和的环。
首先这一定是一个简单环。
想一想这个环是怎么构成的。
考虑环上编号最大的结点
f[u-1][x][y] 和
在 Floyd 的过程中枚举
时间复杂度为
更多参见 最小环 部分内容。
已知一个有向图中任意两点之间是否有连边，要求判断任意两点是否连通。
该问题即是求 图的传递闭包。
我们只需要按照 Floyd 的过程，逐个加入点判断一下。
只是此时的边的边权变为
再进一步用 bitset 优化，复杂度可以到
Bellman–Ford 算法
Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
在国内 OI 界，你可能听说过的「SPFA」，就是 Bellman–Ford 算法的一种实现。
过程
先介绍 Bellman–Ford 算法要用到的松弛操作（Dijkstra 算法也会用到松弛操作）。
对于边
这么做的含义是显然的：我们尝试用
Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。
每次循环是
在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少
但还有一种情况，如果从
负环判断中存在的常见误区
需要注意的是，以
因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。
实现
参考实现
struct Edge {
int u, v, w;
};
vector<Edge> edge;
int dis[MAXN], u, v, w;
constexpr int INF = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0;
bool flag = false; // 判断一轮循环过程中是否发生松弛操作
for (int i = 1; i <= n; i++) {
flag = false;
for (int j = 0; j < edge.size(); j++) {
u = edge[j].u, v = edge[j].v, w = edge[j].w;
if (dis[u] == INF) continue;
// 无穷大与常数加减仍然为无穷大
// 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = true;
}
}
// 没有可以松弛的边时就停止算法
if (!flag) {
break;
}
}
// 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
return flag;
}
class Edge:
def __init__(self, u=0, v=0, w=0):
self.u = u
self.v = v
self.w = w
INF = 0x3F3F3F3F
edge = []
def bellmanford(n, s):
dis = [INF] * (n + 1)
dis[s] = 0
for i in range(1, n + 1):
flag = False
for e in edge:
u, v, w = e.u, e.v, e.w
if dis[u] == INF:
continue
# 无穷大与常数加减仍然为无穷大
# 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
if dis[v] > dis[u] + w:
dis[v] = dis[u] + w
flag = True
# 没有可以松弛的边时就停止算法
if not flag:
break
# 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
return flag
队列优化：SPFA
即 Shortest Path Faster Algorithm。
很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。
SPFA 也可以用于判断
实现
struct edge {
int v, w;
};
vector<edge> e[MAXN];
int dis[MAXN], cnt[MAXN], vis[MAXN];
queue<int> q;
bool spfa(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0, vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
if (cnt[v] >= n) return false;
// 在不经过负环的情况下，最短路至多经过 n - 1 条边
// 因此如果经过了多于 n 条边，一定说明经过了负环
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return true;
}
from collections import deque
class Edge:
def __init__(self, v=0, w=0):
self.v = v
self.w = w
e = [[Edge() for i in range(MAXN)] for j in range(MAXN)]
INF = 0x3F3F3F3F
def spfa(n, s):
dis = [INF] * (n + 1)
cnt = [0] * (n + 1)
vis = [False] * (n + 1)
q = deque()
dis[s] = 0
vis[s] = True
q.append(s)
while q:
u = q.popleft()
vis[u] = False
for ed in e[u]:
v, w = ed.v, ed.w
if dis[v] > dis[u] + w:
dis[v] = dis[u] + w
cnt[v] = cnt[u] + 1 # 记录最短路经过的边数
if cnt[v] >= n:
return False
# 在不经过负环的情况下，最短路至多经过 n - 1 条边
# 因此如果经过了多于 n 条边，一定说明经过了负环
if not vis[v]:
q.append(v)
vis[v] = True
虽然在大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度为
Bellman–Ford 的其他优化
除了队列优化（SPFA）之外，Bellman–Ford 还有其他形式的优化，这些优化在部分图上效果明显，但在某些特殊图上，最坏复杂度可能达到指数级。
- 堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
- 栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。
- LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
- SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
- D´Esopo–Pape 算法：将普通队列换成双端队列，如果一个节点之前没有入队，则将其插入队尾，否则插入队首。
更多优化以及针对这些优化的 Hack 方法，可以看 fstqwq 在知乎上的回答。
Dijkstra 算法
Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。
过程
将结点分成两个集合：已确定最短路长度的点集（记为
初始化
然后重复这些操作：
- 从
集合中，选取一个最短路长度最小的结点，移到 集合中。 - 对那些刚刚被加入
集合的结点的所有出边执行松弛操作。
直到
时间复杂度
朴素的实现方法为每次 2 操作执行完毕后，直接在
可以用堆来优化这一过程：每成功松弛一条边
特别地，可以使用优先队列维护，此时无法执行 Decrease-key 操作，但可以通过每次松弛时重新插入该结点，且弹出时检查该结点是否已被松弛过，若是则跳过，复杂度
这里的堆也可以用线段树来实现，复杂度为
在稀疏图中，
正确性证明
下面用数学归纳法证明，在 所有边权值非负 的前提下，Dijkstra 算法的正确性1。
简单来说，我们要证明的，就是在执行 1 操作时，取出的结点
初始时
接下来用反证法。
设
于是一定存在路径
因为在
下面证明
因此我们证明了，1 操作每次取出的点，其最短路均已经被确定。命题得证。
注意到证明过程中的关键不等式
实现
这里同时给出
朴素实现
struct edge {
int v, w;
};
vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
void dijkstra(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0;
for (int i = 1; i <= n; i++) {
int u = 0, mind = 0x3f3f3f3f;
for (int j = 1; j <= n; j++)
if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
vis[u] = true;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
}
}
}
class Edge:
def __init(self, v=0, w=0):
self.v = v
self.w = w
e = [[Edge() for i in range(MAXN)] for j in range(MAXN)]
INF = 0x3F3F3F3F
def dijkstra(n, s):
dis = [INF] * (n + 1)
vis = [0] * (n + 1)
dis[s] = 0
for i in range(1, n + 1):
u = 0
mind = INF
for j in range(1, n + 1):
if not vis[j] and dis[j] < mind:
u = j
mind = dis[j]
vis[u] = True
for ed in e[u]:
v, w = ed.v, ed.w
if dis[v] > dis[u] + w:
dis[v] = dis[u] + w
优先队列实现
struct edge {
int v, w;
};
struct node {
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;
void dijkstra(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
memset(vis, 0, (n + 1) * sizeof(int));
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}
def dijkstra(e, s):
"""
输入：
e:邻接表
s:起点
返回：
dis:从s到每个顶点的最短路长度
"""
dis = defaultdict(lambda: float("inf"))
dis[s] = 0
q = [(0, s)]
vis = set()
while q:
_, u = heapq.heappop(q)
if u in vis:
continue
vis.add(u)
for v, w in e[u]:
if dis[v] > dis[u] + w:
dis[v] = dis[u] + w
heapq.heappush(q, (dis[v], v))
return dis
Johnson 全源最短路径算法
Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。该算法在 1977 年由 Donald B. Johnson 提出。
任意两点间的最短路可以通过枚举起点，跑
注意到堆优化的 Dijkstra 算法求单源最短路径的时间复杂度比 Bellman–Ford 更优，如果枚举起点，跑
但 Dijkstra 算法不能正确求解带负权边的最短路，因此我们需要对原图上的边进行预处理，确保所有边的边权均非负。
一种容易想到的方法是给所有边的边权同时加上一个正数
但这样的方法是错误的。考虑下图：
但假如我们把每条边的边权加上
新图上
Johnson 算法则通过另外一种方法来给每条边重新标注边权。
我们新建一个虚拟节点（在这里我们就设它的编号为
接下来用 Bellman–Ford 算法求出从
假如存在一条从
接下来以每个点为起点，跑
一开始的 Bellman–Ford 算法并不是时间上的瓶颈，若使用 priority_queue 实现 Dijkstra 算法，该算法的时间复杂度是
正确性证明
为什么这样重新标注边权的方式是正确的呢？
在讨论这个问题之前，我们先讨论一个物理概念——势能。
诸如重力势能，电势能这样的势能都有一个特点，势能的变化量只和起点和终点的相对位置有关，而与起点到终点所走的路径无关。
势能还有一个特点，势能的绝对值往往取决于设置的零势能点，但无论将零势能点设置在哪里，两点间势能的差值是一定的。
接下来回到正题。
在重新标记后的图上，从
化简后得到：
无论我们从
为了方便，下面我们就把
上面的新图中
到这里我们的正确性证明已经解决了一半——我们证明了重新标注边权后图上的最短路径仍然是原来的最短路径。接下来我们需要证明新图中所有边的边权非负，因为在非负权图上，Dijkstra 算法能够保证得出正确的结果。
根据三角形不等式，图上任意一边
这样，我们就证明了 Johnson 算法的正确性。
不同方法的比较
| 最短路算法 | Floyd | Bellman–Ford | Dijkstra | Johnson |
|---|---|---|---|---|
| 最短路类型 | 每对结点之间的最短路 | 单源最短路 | 单源最短路 | 每对结点之间的最短路 |
| 作用于 | 任意图 | 任意图 | 非负权图 | 任意图 |
| 能否检测负环？ | 能 | 能 | 不能 | 能 |
| 时间复杂度 |
注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。
输出方案
开一个 pre 数组，在更新距离的时候记录下来后面的点是如何转移过去的，算法结束前再递归地输出路径即可。
比如 Floyd 就要记录 pre[i][j] = k;，Bellman–Ford 和 Dijkstra 一般记录 pre[v] = u。
参考资料与注释
-
《算法导论（第 3 版中译本）》，机械工业出版社，2013 年，第 384 - 385 页。 ↩
创建日期: 2018年7月11日