目录¶
- 最短路算法
- 最小生成树
1 最短路算法¶
1.1 Floyd 算法¶
用来求任意两个结点之间的最短路，复杂度比较高，但是常数小，容易实现（只有三个 for）。适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有负环）。
实现¶
我们定义一个数组 f[k][x][y]，表示只允许经过结点 \(1\) 到 \(k\)，结点 \(x\) 到结点 \(y\) 的最短路长度。显然，f[n][x][y] 就是结点 \(x\) 到结点 \(y\) 的最短路长度。
接下来考虑如何求出 f 数组的值：
f[0][x][y]：\(x\) 与 \(y\) 的边权，或者为 \(0\)，或者为 \(+\infty\)。f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k] + f[k-1][k][y])
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]);
}
}
}
应用¶
给一个正权无向图，找一个最小权值和的环
首先这一定是一个简单环。想一想这个环是怎么构成的。
考虑环上编号最大的结点 \(u\)。
f[u-1][x][y] 和 \((u,x),(u,y)\) 共同构成了环。
在 Floyd 的过程中枚举 \(u\)，计算这个和的最小值即可。
时间复杂度为 \(O(n^3)\)。
已知一个有向图中任意两点之间是否有连边，要求判断任意两点是否连通
该问题即是求 图的传递闭包。 我们只需要按照 Floyd 的过程，逐个加入点判断一下。 只是此时的边权变为 \(1/0\)，而取 \(\min\) 变成了 或 运算。 再进一步用 bitset 优化，复杂度可以到 \(O(\frac{n^3}{w})\)。
// std::bitset<SIZE> f[SIZE];
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (f[i][k]) f[i] = f[i] | f[k];
f[i][j] = 1 表示结点 i 可以到达结点 j。
f[i] 表示 i 直接可达的所有结点。
1.2 Bellman-Ford 算法¶
Bellman-Ford 算法是基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。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\) 点出发，能够抵达一个负环。
负环判断中存在的常见误区
需要注意的是，以 \(S\) 点为源点跑 Bellman-Ford 算法时，如果没有给出存在负环的结果，只能说明从 \(S\) 点出发不能抵达一个负环，而不能说明图上不存在负环。 因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 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;
}
队列优化：SPFA¶
即 Shortest Path Faster Algorithm。
很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护 哪些结点可能会引起松弛操作，就能只访问必要的边了。
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 算法）
1.3 Dijkstra 算法¶
Dijkstra 算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。
过程¶
将结点分成两个集合：已确定最短路长度的点集（记为 \(S\) 集合）和未确定最短路长度的点集（记为 \(T\) 集合）。一开始所有的点都属于 \(T\) 集合。
初始化 \(dis(s) = 0\)，其他点的 \(dis\) 均为 \(+\infty\)。
然后重复这些操作：
- 从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中。
- 对那些刚刚被加入 \(S\) 集合的结点的所有出边执行松弛操作。
直到 \(T\) 集合为空，算法结束。
优先队列实现¶
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});
}
}
}
}
时间复杂度 \(O(m\log n)\)
2 最小生成树¶
无向图的 最小生成树（MST） 为边权和最小的生成树。
2.1 Kruskal 算法¶
Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。
前置知识：并查集、图的存储。
算法过程：
- 将所有边按权值从小到大排序
- 依次考虑每条边，如果加入该边不会形成环，则加入
- 使用并查集判断连通性
- 直到选择了 \(n-1\) 条边为止
算法虽简单，但需要相应的数据结构来支持……具体来说，维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。
抽象一点地说，维护一堆 集合，查询两个元素是否属于同一集合，合并两个集合。
其中，查询两点是否连通和连接两点可以使用并查集维护。
如果使用 \(O(m\log m)\) 的排序算法，并且使用 \(O(m\alpha(m,n))\) 或 \(O(m\log n)\) 的并查集，就可以得到时间复杂度为 \(O(m\log m)\) 的 Kruskal 算法。
2.2 Prim 算法¶
Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。
具体来说，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。
其实跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。
堆优化的方式类似 Dijkstra 的堆优化，但如果使用二叉堆等不支持 \(O(1)\) decrease-key 的堆，复杂度就不优于 Kruskal，常数也比 Kruskal 大。所以，一般情况下都使用 Kruskal 算法，在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但 不一定 实际跑得更快。
// 使用二叉堆优化的 Prim 算法
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int N = 5050, M = 2e5 + 10;
struct E {
int v, w, x;
} e[M * 2];
int n, m, h[N], cnte;
void adde(int u, int v, int w) { e[++cnte] = E{v, w, h[u]}, h[u] = cnte; }
struct S {
int u, d;
};
bool operator<(const S& x, const S& y) { return x.d > y.d; }
priority_queue<S> q;
int dis[N];
bool vis[N];
int res = 0, cnt = 0;
void Prim() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
q.push({1, 0});
while (!q.empty()) {
if (cnt >= n) break;
int u = q.top().u, d = q.top().d;
q.pop();
if (vis[u]) continue;
vis[u] = true;
++cnt;
res += d;
for (int i = h[u]; i; i = e[i].x) {
int v = e[i].v, w = e[i].w;
if (w < dis[v]) {
dis[v] = w, q.push({v, w});
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1, u, v, w; i <= m; ++i) {
cin >> u >> v >> w, adde(u, v, w), adde(v, u, w);
}
Prim();
if (cnt == n)
cout << res;
else
cout << "No MST.";
return 0;
}
2.3 最小生成树的唯一性¶
考虑最小生成树的唯一性。如果一条边不在 MST 的边集中，并且可以替换与其权值相同并且在 MST 边集的另一条边，那么这个 MST 就是不唯一的。
对于 Kruskal 算法，只要计算为当前权值的边可以放几条，实际放了几条，如果这两个值不一样，那么就说明这几条边与之前的边产生了一个环（这个环中至少有两条当前权值的边，否则根据并查集，这条边是不能放的），即最小生成树不唯一。
寻找权值与当前边相同的边，我们只需要记录头尾指针，用单调队列即可在 \(O(\alpha(m))\)（\(m\) 为边数）的时间复杂度里解决这个问题。（基本与原算法时间相同）
2.4 次小生成树¶
求解方法¶
- 求出无向图的最小生成树 \(T\)，设其权值和为 \(M\)
- 遍历每条未被选中的边 \(e = (u, v, w)\)，找到 \(T\) 中 \(u\) 到 \(v\) 路径上边权最大的一条边 \(e^{'} = (s, t, w^{'})\)，则在 \(T\) 中以 \(e\) 替换它，可得到一棵权值和为 \(M^{'} = M + w - w^{'}\) 的新生成树
- 对所有替换得到的答案 \(M^{'}\) 取最小值即可。
可以使用求 LCA 的倍增算法来预处理 \(u, v\) 路径上的边权最大值。
2.5 瓶颈生成树¶
定义¶
无向图 \(G\) 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 \(G\) 的所有生成树中最小。
性质¶
最小生成树是瓶颈生成树的充分不必要条件。可以用反证法证明。
2.6 最小瓶颈路¶
定义¶
无向图 \(G\) 中 \(x\) 到 \(y\) 的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有 \(x\) 到 \(y\) 的简单路径中是最小的。
性质¶
根据最小生成树定义，\(x\) 到 \(y\) 的最小瓶颈路上的最大边权等于最小生成树上 \(x\) 到 \(y\) 路径上的最大边权。虽然最小生成树不唯一，但是每种最小生成树 \(x\) 到 \(y\) 路径的最大边权相同且为最小值。也就是说，每种最小生成树上的 \(x\) 到 \(y\) 的路径均为最小瓶颈路。
但是，并不是所有最小瓶颈路都存在一棵最小生成树满足其为树上 \(x\) 到 \(y\) 的简单路径。
总结¶
| 算法 | 时间复杂度 | 适用条件 | 特点 |
|---|---|---|---|
| Floyd | \(O(n^3)\) | 任意图，无负环 | 全源最短路 |
| Bellman-Ford | \(O(nm)\) | 有负权边 | 可检测负环 |
| SPFA | \(O(nm)\)（最坏） | 有负权边 | 队列优化 |
| Dijkstra | \(O(m\log n)\) | 非负权图 | 单源最短路 |
| Kruskal | \(O(m\log m)\) | 无向图 | 基于并查集 |
| Prim | \(O(m\log n)\) | 无向图 | 类似 Dijkstra |