最短路¶
前置信息¶
记号¶
为了方便叙述，这里先给出下文将会用到的一些记号的含义。
- \(u\)为图上点的数量，\(m\)为图上边的树木
- \(s\)为最短路的源点
- \(D(u)\)为\(s\)点到\(u\)点的**实际**最短路长度
- \(dis(u)\)为\(s\)点到\(u\)点到**估计**最短路长度。任何时候都有\(dis(u) \geq D(u)\)。特别的，当最短路算法终止时，应有\(dis(u)=D(u)\)。
- \(w(u,v)\)为\((u,v)\)这条边的边权。
性质¶
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。
对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过\(n\)，边数不会超过\(n-1\)。
Floyd 算法¶
是用来求任意两个结点之间的最短路的。
复杂度比较高，但是常数小，容易实现（只有三个 for）。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
实现¶
我们定义一个数组 f[k][x][y]，表示只允许经过结点\(1\)到\(k\)（也就是说，在子图\(V'=1,2,...,k\)中的路径，注意，\(x\)与\(y\)不一定在这个子图中），结点\(x\)到结点\(y\)的最短路长度。
很显然，f[n][x][y] 就是结点\(x\)到结点\(y\)的最短路长度（因为\(V'=1,2,...,n\)即为\(V\)本身，其表示的最短路径就是所求路径)。
接下来考虑如何求出 f 数组的值。
f[0][x][y]：\(x\)与\(y\)的边权，或者\(0\)，或者\(+\infty\)（当\(x\)与\(y\)间有直接相连的边的时候，为它们的边权；当\(x=y\)的时候为零，因为到本身的距离为零；当\(x\)与\(y\)没有直接相连的边的时候，为\(+\infty\)）。
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]，为不经过\(k\)点的最短路径，而 f[k-1][x][k]+f[k-1][k][y]，为经过了\(k\)点的最短路)。
上面两行都显然是对的，所以说这个做法空间是\(O(N^3)\)，我们需要依次增加问题规模（\(k\)从\(1\)到\(n\)），判断任意两点在当前问题规模下的最短路。
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[k][x][y] = min(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])。
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
Bellman–Ford 算法¶
Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
在国内 OI 界，你可能听说过的「SPFA」，就是 Bellman–Ford 算法的一种实现。
过程¶
对于边\((u,v)\)，**松弛操作**对应下面的式子：\(dis(v)=min(dis(v), dis(u) + w(u,v))\)。
这么做的含义是显然的：我们尝试用\(S\rightarrow u \rightarrow v\)（其中\(S \rightarrow u\)的路径取最短路）这条路径去更新\(v\)点最短路的长度。
Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。
每次循环是\(O(m)\)的，那么最多会循环多少次呢？
在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少\(+1\)，而最短路的边数最多为\(n-1\)，因此整个算法最多执行\(n-1\)轮松弛操作。故总时间复杂度为\(O(nm)\)。
但还有一种情况，如果从\(S\)点出发，抵达一个负环时，松弛操作会无休止地进行下去。因此如果第\(n\)轮循环时仍然存在能松弛的边，说明从\(S\)点出发，能够抵达一个负环。
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;
}
队列优化：SPFA¶
即 Shortest Path Faster Algorithm。
很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。
SPFA 也可以用于判断\(s\)点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少\(n\)条边时，说明\(s\)点可以抵达一个负环。
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;
}
虽然在大多数情况下 SPFA 跑得很快，但其最坏情况下的时间复杂度为\(O(nm)\)，将其卡到这个复杂度也是不难的，所以考试时要谨慎使用（在没有负权边时最好使用 Dijkstra 算法，在有负权边且题目中的图没有特殊性质时，若 SPFA 是标算的一部分，题目不应当给出 Bellman–Ford 算法无法通过的数据范围)。
Dijkstra 算法¶
Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。
过程¶
将结点分成两个集合：已确定最短路长度的点集（记为\(S\)集合）的和未确定最短路长度的点集（记为\(T\)集合）。一开始所有的点都属于\(T\)集合。
初始化：\(dis(s)=0\)，其它点的\(dis\)均为\(+ \infty\)
然后重复这些操作：
- 从\(T\)集合中，选取一个最短路长度最小的结点，移到\(S\)集合中。
- 对那些刚刚被加入\(S\)集合的结点的所有**出边**执行松弛操作。
直到\(T\)集合为空，算法结束。
暴力实现¶
不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在\(T\)集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为\(O(m)\)，1操作总时间复杂度为\(O(n^2)\)，全过程的时间复杂度为\(O(n^2+m)=O(n^2)\)
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;
}
}
}
优先队列实现¶
如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是\(O(m)\)的，时间复杂度为\(O(m \ log \ m)\)。
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});
}
}
}
时间复杂度¶
有多种方法来维护 1 操作中最短路长度最小的结点，不同的实现导致了 Dijkstra 算法时间复杂度上的差异。