图论——最短路 学习笔记
图论——最短路 学习笔记
其实是复习性质的,主要是总结,证明什么的,等上大学再说。
定义
- 单源最短路:从一个点 \(q\) 出发,到其他所有点的最短路。
- 全源最短路:任意两点见最短路。
算法对比
算法 | Floyd | Johnson | Bellman–Ford | SPFA | Dijkstra |
---|---|---|---|---|---|
类型 | 全源 | 全源 | 单源 | 单源 | 单源 |
作用于 | 任意图 | 任意图 | 任意图 | 任意图 | 非负权图 |
检测负环 | 能 | 能 | 能 | 能 | 不能 |
时间复杂度 | \(\mathcal{O}(n^3)\) | \(\mathcal{O}(nm \log m)\) | \(\mathcal{O}(nm)\) | \(\mathcal{O}(m)\)-\(\mathcal{O}(nm)\) | \(\mathcal{O}(n^2)\)-\(\mathcal{O}(m \log n)\) |
总结:
- 没有负环用 dijk,理论上,稠密图(有 \(m\) 与 \(n^2\) 同阶)用朴素的,稀疏图(有 \(m \ll n^2\) 的)用堆优化。
- 有负环优先用 SPFA,即使她被卡也比 BF 快一点。
- 多源用 Floyd,因为不会 Johnson。
Dijkstra
过程
设两个集合:「已确定最短路长度的集合 \(S\)」和「未确定最短路长度的集合 \(T\)」,每次从 \(T\) 中选取一个最近的,加入集合 \(S\) 并松弛,更新其他点的最短路。直到 \(T\) 集合为空。
代码:
int n, m, g[N][N];
array<int, N> dis, vis; // 到这个点的最短路,是否已经确定最短路
int gett() {
int t = -1;
for (int i = 1; i <= n; ++j)
if (!st[i] && (t == -1 || dis[t] > dis[i])) t = i;
return t;
} void dijkstra(int s) {
dis.fill(0x3f); dis[1] = 0;
for (int i = 0; i < n; ++i) {
int t = gett(); st[t] = true;
for (int j = 1; j <= n; ++j)
dist[j] = min(dist[j], dist[t] + g[t][j]);
} return (void)("rp++");
}
时间复杂度:\(\mathcal{O}(n^2)\)。
堆优化
每成功松弛一条边 \((u,v)\) ,就将 \(v\) 插入堆中,如果 \(v\) 已经在堆中,直接修改相应元素的权值即可,每次查找操作直接取堆顶结点即可。
代码:
using pii = pair<int, int>;
array<int, N> dis, st; // 到这个点的最短路,是否在堆中
#define v e[i]
void dijkstra(int s) {
dis.fill(0x3f); dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> heap;
heap.push({0, s}); while (heap.size()) {
pii t = heap.top(); heap.pop();
int u = t.second, d = t.first;
if (st[u]) continue; st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
if (dist[v] > d + w[i]) dis[v] = d + w[i], heap.push({dis[v], v});
} return (void)("rp++");
}
共计 \(\mathcal{O}(m)\) 次二叉堆上的插入操作,\(\mathcal{O}(n)\) 次删除堆顶操作,而插入和删除的时间复杂度均为 \(\mathcal{O}(\log n)\),故时间复杂度:\(\mathcal{O}((m+n) \log n)=\mathcal{O}(m \log n)\)。
Bellman–Ford
不断尝试对图上每一条边进行松弛。我们每进行一轮循环,就对图上所有的边都尝试进行一次松弛操作,当一次循环中没有成功的松弛操作时,算法停止。
因为一个图的最短路,在没有负环的情况下,最长只能是 \(n-1\) 条边,所以松弛 \(n-1\) 轮即可。
因此可以得出此算法求不超过 \(k\) 条边的最短路的方法,即松弛 \(k\) 轮。
int n, m, k;
struct Edge { int a, b, w; } edges[M];
array<int, N> dis;
void bellman_ford(int s) {
dis.fill(INF); dis[s] = 0;
for (int i = 0; i < k; ++i) { // 不超过 k 条边的最短路
auto bak = dis; // 需要备份下来处理
bool flag = false;
for (int j = 0 ; j < m ; ++j)
if (bak[edges[j].a] + edges[j].w < dis[edges[j].b])
dis[edges[j].b] = bak[edges[j].a] + edges[j].w, flag = true;
if (!flag) break;
}
}
在最短路存在的情况下,由于一次松弛操作会使最短路的边数至少 \(+1\),而最短路的边数最多为 \(n-1\),因此整个算法最多执行 \(n-1\) 轮松弛操作。故总时间复杂度为 \(\mathcal O(nm)\)。
队列优化 Bellman–Ford——SPFA
SPFA 说的通俗点叫 Bellman–Ford 的队列优化(BFS)版。
原理是,只有上一次被松弛的结点,所连接的边,才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」,就能只访问必要的边了。
代码:
int h[N], w[N], e[N], ne[N], idx;
array<int, N> dis, st; // 到这个点的最短路,是否在队列中
#define v e[i]
void spfa(int s) {
dis.fill(INF); dist[1] = 0;
queue<int> q; q.push(1);
st[1] = true;
while (q.size()) {
int u = q.front(); q.pop();
st[u] = false;
for (int i = h[u] ; i != -1 ; i = ne[i])
if (dist[v] > dis[u] + w[i]) {
dist[v] = dis[u] + w[i];
if (!st[v]) q.push(v), st[v] = true;
}
}
}
栈优化 Bellman–Ford——找负环
通常用于判负环,不用像 SPFA 那样判进队次数的原因是:DFS 在栈内的只有祖先,而 BFS 有非祖先。
int dis[N], vis[N]; // 提前将 dis 赋为 INF
bool dfs_spfa(int u) {
if (vis[u]) return true; vis[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
if (dis[e[i]] > dis[u] + w[i]) {
dis[e[i]] = dis[u] + w[i];
if (dfs_spfa(e[i])) return true;
} return vis[u] = false;
}
Floyd
一个很实用的全源最短路解法,特点是好写,容易拓展。
时间复杂度:\(\mathcal O(n^3)\)。
代码:
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]);
Johnson
不会,现阶段不打算学。
Reference
[1] https://oi-wiki.org/graph/shortest-path/
本文来自博客园,作者:RainPPR,转载请注明原文链接:https://www.cnblogs.com/RainPPR/p/shortest-path.html
热门相关:娇妻太甜:老公,要抱抱 你好,墨先生 至尊剑皇 都市捉妖人 至尊剑皇