图论——最短路 学习笔记
其实是复习性质的，主要是总结，证明什么的，等上大学再说。
定义
- 单源最短路：从一个点 \(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。
前言
如果是 DAG 也可以跑拓扑，速度更快！
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
不会，现阶段不打算学。文章来源：https://www.toymoban.com/news/detail-746187.html
Reference
[1] https://oi-wiki.org/graph/shortest-path/文章来源地址https://www.toymoban.com/news/detail-746187.html
到了这里，关于图论——最短路 学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
