订阅更新(RSS/Atom): 又是一年 CSP 复赛，已经一年没写过最短路了，赶紧复习一下。 Floyd 算法是用来求所有结点对最短路的。适用于所有不含负环的图。这个算法运用了 DP 的思想。首先定义 f[k][i][j] 表示只允许经过结点 $1, 2, \cdots k$，结点 $i$ 到结点 $j$ 的最短路长度。初始化时，f[k][i][i] = 0，其他赋值为 $+\infty$。可以有 f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j])（f[k-1][i][j] 表示不经过 $k$ 点的最短路径，f[k-1][i][k] + f[k-1][k][j] 表示经过 $k$ 点的最短路径）。这时可以发现，数组的第一维是可以忽略的，所以直接写成 f[i][j] = min(f[i][j], f[i][k] + f[k][j])。时间、空间复杂度均为 $O(N^3)$。实现： 1 2 3 4 for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); Luogu-P6175 无向图的最小环问题记原图中 $i,j$ 之间边的边权为 $val\left(i,j\right)$。我们注意到 Floyd 算法有一个性质：在最外层循环到点 $k$ 时（尚未开始第 $k$ 次循环），最短路数组 $dis$ 中，$dis_{i,j}$ 表示的是从 $i$ 到 $j$ 且仅经过编号在 $\left[1, k\right)$ 区间中的点的最短路。由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 $w$，环上与 $w$ 相邻两侧的两个点为 $i,j$，则在最外层循环枚举到 $k=w$ 时，该环的长度即为 $dis_{i,j}+val\left(j,w\right)+val\left(w,i\right)$。故在循环时对于每个 $k$ 枚举满足 $i G[MAXN]; int dis[MAXN]; bool bellmanford() { memset(dis, 0x3f, sizeof dis); dis[s] = 0; bool flag; // 判断有没有松弛 for (int i = 0; i < n; i++) { flag = false; for (int u = 1; u <= n; u++) { if (dis[u] == 0x3f3f3f3f) continue; // 无穷大与常数加减仍然为无穷大 // 因此最短路长度为 inf 的点引出的边不可能发生松弛操作 for (auto j : G[u]) { int v = j.to, w = j.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; flag = true; } } } // 没有可以松弛的边时就停止算法 if (!flag) break; } return flag; // 第 n 轮循环仍然可以松弛时（flag==true）说明 s 点可以抵达一个负环 } 关于 SPFA：它死了很多时候我们并不需要那么多无用的松弛操作。显然，只有上一次被松弛的结点所连接的边，才有可能引起下一次的松弛操作。那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。 SPFA 也可以用于判断 $s$ 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 $n$ 条边时，说明 $s$ 点可以抵达一个负环。慎用！SPFA 在最坏情况下时间复杂度和 Bellman-Ford 一样为 $O(nm)$。如果没有负权边时，一定要使用 Dijkstra 算法。实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 vector G[MAXN]; bool vis[MAXN]; int dis[MAXN], cnt[MAXN]; // cnt 记录最短路经过的边数 bool SPFA() { memset(dis, 0x3f, sizeof dis); dis[s] = 0; queue q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (auto i : G[u]) { int v = i.to, w = i.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; cnt[v] = cnt[u] + 1; // 在不经过负环的情况下，最短路至多经过 n - 1 条边 // 因此如果经过了多于 n 条边，一定说明经过了负环 if (cnt[v] >= n) return true; if (!vis[v]) { vis[v] = 1; q.push(v); } } } } return false; } Dijkstra 算法要求所有边的权重都为非负值，运用贪心策略。我们把结点分为两个集合：已确定最短路长度的点集 $S$ 和未确定最短路长度的点集 $T$。算法重复从 $T$ 中选择最短路径估计最小的结点 $u$，将 $u$ 加入到集合 $S$，然后对所有从 $u$ 发出的边进行松弛。暴力 Dijkstra 实现需要每次暴力寻找一个最小值，共寻找 $n$ 次，为 $O(n^2)$。每条边可能要进行一次松弛，为 $O(m)$。因此时间复杂度是 $O(n^2+m) = O(n^2)$。实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int n, m, s; struct edge { int to, w; }; vector G[MAXN]; bool used[MAXN]; int dis[MAXN]; void dijkstra() { memset(dis, 0x3f, sizeof dis); dis[s] = 0; for (int i = 1; i <= n; i++) { int minn = n + 1; for (int j = 1; j <= n; j++) if (!used[j] && dis[j] < dis[minn]) minn = j; used[minn] = 1; for (auto j : G[minn]) dis[j.to] = min(dis[j.to], dis[minn] + j.w); // RELAX } } 可以用优先队列来寻找最短路长度的最小值，时间复杂度优化为 $O(m\log m)$。实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 struct edge { int to, w; bool operator>(const edge b) { return w > b.w; } }; vector G[MAXN]; bool used[MAXN]; int dis[MAXN]; priority_queue, greater<>> pq; void dijkstra() { memset(dis, 0x3f, sizeof dis); dis[s] = 0; pq.push({s, 0}); while (!pq.empty()) { edge t = pq.top(); pq.pop(); if (used[t.to]) continue; used[t.to] = 1; for (auto i : G[t.to]) { int v = i.to, w = i.w; if (dis[v] > dis[t.to] + w) { dis[v] = dis[t.to] + w; pq.push({v, dis[v]}); } } } } 要注意 priority_queue 默认是大根堆。换成小根堆需要重载 > 运算符，并使用 priority_queue, greater<>> pq;。在松弛成功后，需要重新修改结点 v 的优先级，但是 STL 中优先队列不允许这样的操作。所以我们只能将新的元素插入优先队列（这样做不会影响正确性，因为新的元素的最短路长度更小，会更早出队），为了避免结点重复扩展，如果发现新取出的结点已经扩展过（used[]）就应该扔掉。另一种方法是把 if (used[t.to]) 换成 if (t.w == dis[t.to])（dis[t.to] 一定是当前最短的）。最短路算法 Floyd Bellman-Ford Dijkstra 最短路类型每对结点之间的最短路单源最短路单源最短路作用于任意图任意图非负权图能否检测负环？能能不能推荐作用图的大小小中/小大/中时间复杂度 $O(N^3)$ $O(NM)$ $O(M\log M)$ 注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。比如 Floyd 就要记录 pre[i][j] = k，Bellman-Ford 和 Dijkstra 一般记录 pre[v] = u。 UPDATE after CSP-S 2022：对于我这种不会变通的 sha b*，必须得做个笔记：对于一些特殊的图，也可以用 BFS 求最短路：在一个无权图上求从起点到其他所有点的最短路径。进一步地，用这个方法也可以 $O(nm)$ 求全源最短路径。[CSP-S 2022] 假期计划就用到了这一个方法，但我却使用了 Floyd ！！！从一开始就葬送了这道题！！！在一个边权为 0/1 的图上求最短路（0-1 BFS，双端队列 BFS）例题：「BalticOI 2011 Day1」打开灯泡 Switch the Lamp On OI Wiki CC BY-SA 4.0 《算法导论》《算法竞赛入门经典》

最短路笔记

Floyd-Warshall 算法