0 前言
总结一些最短路问题的常用模板 (这回是小坑了)
1 Floyd-Warshall - 多源最短路
基础的动态规划,经典的三重循环,最简单的最短路算法
1.1 原理
AcWing 854. Floyd求最短路
设 F i , j F_{i,j} F i , j 表示点 i i i 到点 j j j 的最短路径,枚举中转点 k k k ,每次通过中转点更新最短路径,转移方程 F i , j = m i n { G i , j , F i , k + F k , j } F_{i,j} = min\left\{ G_{i,j}, F_{i,k} + F_{k,j} \right\} F i , j = m i n { G i , j , F i , k + F k , j } ,时间复杂度 O ( N 3 ) O(N^3) O ( N 3 ) .
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 30 31 32 33 34 35 36 37 38 39 40 #include <bits/stdc++.h> using namespace std;const int N = 500 + 5 ;const int INF = 0x3f3f3f3f ;int n, m, k;int f[N][N];int main () { scanf ("%d%d%d" , &n, &m, &k); for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) f[i][j] = i == j ? 0 : INF; for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); f[u][v] = min (f[u][v], w); } for (int k = 1 ; k <= n; k++) for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) if (f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j]; while (k--) { int u, v; scanf ("%d%d" , &u, &v); if (f[u][v] > INF / 2 ) puts ("impossible" ); else printf ("%d\n" , f[u][v]); } return 0 ; }
1.2 应用
1.2.1 求图的传递闭包
例题
Luogu B3611 【模板】传递闭包
给定一张点数为 n n n 的有向图的邻接矩阵,图中不包含自环,求该有向图的传递闭包。
一张图的邻接矩阵定义为一个 n × n n\times n n × n 的矩阵 A = ( a i j ) n × n A=(a_{ij})_{n\times n} A = ( a i j ) n × n ,其中
a i j = { 1 , i 到 j 存在直接连边 0 , i 到 j 没有直接连边 a_{ij}=\left\{
\begin{aligned}
1,i\ 到\ j\ 存在直接连边 \\
0,i\ 到\ j\ 没有直接连边 \\
\end{aligned}
\right.
a i j = { 1 , i 到 j 存 在 直 接 连 边 0 , i 到 j 没 有 直 接 连 边
一张图的传递闭包定义为一个 n × n n\times n n × n 的矩阵 B = ( b i j ) n × n B=(b_{ij})_{n\times n} B = ( b i j ) n × n ,其中
b i j = { 1 , i 可以直接或间接到达 j 0 , i 无法直接或间接到达 j b_{ij}=\left\{
\begin{aligned}
1,i\ 可以直接或间接到达\ j \\
0,i\ 无法直接或间接到达\ j \\
\end{aligned}
\right.
b i j = { 1 , i 可 以 直 接 或 间 接 到 达 j 0 , i 无 法 直 接 或 间 接 到 达 j
题解
对 F l o y d Floyd F l o y d 算法进行简单变形,记 f i , j f_{i,j} f i , j 表示 i i i 可以直接或间接到达 j j j
得到状态转移方程为 f i , j = ∨ k ( f i , k ∧ f k , j ) f_{i,j} = \lor_{k} (f_{i,k} \land f_{k, j}) f i , j = ∨ k ( f i , k ∧ f k , j )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;const int N = 100 + 5 ;int n;bool a[N][N];int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) scanf ("%d" , &a[i][j]); for (int k = 1 ; k <= n; k++) for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) a[i][j] |= a[i][k] & a[k][j]; for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) printf ("%d%c" , a[i][j], j == n ? '\n' : ' ' ); return 0 ; }
2 Dijkstra - 单源最短路
2.1 原理及优化
Luogu P4779【模板】单源最短路径(标准版)
2.1.1 算法原理
每次找到离源点最近且未经松弛的点,以该点为中转点,对连接该点的边进行 松弛 操作.
2.1.2 优化一:优先队列
我们发现找离源点最近的边的过程比较繁琐,可以考虑将所有松弛成功的距离和点存入 优先队列 中,每次取出离当前节点最近且还未松弛过的点
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <bits/stdc++.h> using namespace std;const int N = 1e5 + 5 ;vector<pair<int , int >> E[N]; int dis[N];bool vis[N];priority_queue<pair<int , int >, vector<pair<int , int >>, greater<pair<int , int >>> Q; inline void Dijkstra (int s) { memset (vis, false , sizeof (vis)); memset (dis, 0x3f , sizeof (dis)); dis[s] = 0 ; Q.push (make_pair (0 , s)); while (!Q.empty ()) { int u = Q.top ().second; Q.pop (); if (vis[u]) continue ; vis[u] = true ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; Q.push (make_pair (dis[v], v)); } } } } int n, m, s;int main () { scanf ("%d%d%d" , &n, &m, &s); for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, w)); } Dijkstra (s); for (int i = 1 ; i <= n; i++) printf ("%d%c" , dis[i], i == n ? '\n' : ' ' ); return 0 ; }
2.1.3 优化二:配对堆
上述优化其实有一个缺点,就是同一个点可能多次进入优先队列,其实我们可以使用 配对堆 直接修改该点的值来对时空复杂度进行优化
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <bits/stdc++.h> #include <bits/extc++.h> using namespace std;const int N = 1e5 + 5 ;vector<pair<int , int >> E[N]; int dis[N];__gnu_pbds::priority_queue<pair<int , int >, greater<pair<int , int >>, __gnu_pbds::pairing_heap_tag> Q; __gnu_pbds::priority_queue<pair<int , int >, greater<pair<int , int >>, __gnu_pbds::pairing_heap_tag>::point_iterator idx[N]; inline void Dijkstra (int s) { memset (dis, 0x3f , sizeof (dis)); dis[s] = 0 ; idx[s] = Q.push (make_pair (0 , s)); while (!Q.empty ()) { int u = Q.top ().second; Q.pop (); for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (idx[v] != 0 ) Q.modify (idx[v], make_pair (dis[v], v)); else idx[v] = Q.push (make_pair (dis[v], v)); } } } } int n, m, s;int main () { scanf ("%d%d%d" , &n, &m, &s); for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, w)); } Dijkstra (s); for (int i = 1 ; i <= n; i++) printf ("%d%c" , dis[i], i == n ? '\n' : ' ' ); return 0 ; }
2.2 应用
2.2.1 同余最短路问题
例题
Luogu P3403 跳楼机
给定 x , y , z , h ( x < y < z < h ) x, y, z, h (x < y < z < h) x , y , z , h ( x < y < z < h ) ,对于 k ∈ [ 1 , h ] k \in [1, h] k ∈ [ 1 , h ] ,求有多少个 k k k 能够满足 a x + b y + c z = k ax+by+cz=k a x + b y + c z = k .
题解
设 d i d_i d i 为满足 ( b y + c z ) ≡ 1 ( m o d x ) (by+cz) \equiv 1 (mod \space x) ( b y + c z ) ≡ 1 ( m o d x ) 的最小 ( b y + c z ) (by+cz) ( b y + c z ) ,这里记为 p p p .
可以得到两个转移方程:
类比三角形不等式,我们可以得到一个建图方案,进而通过单源最短路径算法求得 d i d_i d i .
这样,即可获得答案 ∑ i = 0 x − 1 ( h − d i x + 1 ) \sum_{i=0}^{x - 1}\left(\frac{h - d_i}{x} + 1\right) ∑ i = 0 x − 1 ( x h − d i + 1 )
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> using namespace std;const int N = 1e5 + 5 ;const long long INF = LLONG_MAX;long long h;int x, y, z;vector<pair<int , int >> E[N]; bool vis[N];long long dis[N];priority_queue<pair<long long , int >, vector<pair<long long , int >>, greater<pair<long long , int >>> Q; void Dijkstra (int s) { memset (vis, false , sizeof (vis)); for (int i = 0 ; i < x; i++) dis[i] = INF; dis[0 ] = 1 ; Q.push (make_pair (0 , 0 )); while (!Q.empty ()) { int u = Q.top ().second; Q.pop (); if (vis[u]) continue ; vis[u] = true ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; Q.push (make_pair (dis[v], v)); } } } } int main () { scanf ("%lld" , &h); scanf ("%d%d%d" , &x, &y, &z); for (int i = 0 ; i < x; i++) { E[i].push_back (make_pair ((i + y) % x, y)); E[i].push_back (make_pair ((i + z) % x, z)); } Dijkstra (0 ); long long ans = 0 ; for (int i = 0 ; i < x; i++) if (h >= dis[i]) ans += (h - dis[i]) / x + 1 ; printf ("%lld\n" , ans); return 0 ; }
3 Bellman-Ford - 单源最短路
3.1 原理及优化
Luogu P3371【模板】单源最短路径(弱化版)
3.1.1 原理
对所有的边进行 n − 1 n-1 n − 1 次 松弛 操作
3.1.2 常见优化:队列优化
关于SPFA,它死了
用一个队列维护上一轮松弛中最短路程发生变化的节点,每次对队首的节点的出边进行松弛操作,如果达到的点在队列中,就没有必要再次入队,同样的方式处理直到队列为空时即可获得单源最短路径。
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <bits/stdc++.h> using namespace std;const int N = 10000 + 5 ;int n, m, s;vector<pair<int , int >> E[N]; int dis[N];bool vis[N];queue<int > Q; void SPFA () { for (int i = 1 ; i <= n; i++) dis[i] = 0x7fffffff ; dis[s] = 0 ; vis[s] = true ; Q.push (s); while (!Q.empty ()) { int u = Q.front (); Q.pop (); vis[u] = false ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > (long long )dis[u] + w) { dis[v] = dis[u] + w; if (vis[v]) continue ; vis[v] = true ; Q.push (v); } } } } int main () { scanf ("%d%d%d" , &n, &m, &s); for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, w)); } SPFA (); for (int i = 1 ; i <= n; i++) printf ("%d%c" , dis[i], i == n ? '\n' : ' ' ); return 0 ; }
3.2 应用
3.2.1 判断图中是否存在负环
例题
Luogu P3385【模板】负环
给定一个 n n n 个点的有向图,请求出图中是否存在从顶点 1 1 1 出发能到达 的负环。
负环的定义是:一条边权之和为负数的回路。
题解
若第 n n n 轮迭代仍有结点的最短路能被更新,则说明图中存在负环
这里来个DFS版的Bellman-Ford算法(会超时)
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <bits/stdc++.h> using namespace std;const int N = 2e3 + 5 ;const int M = 3e3 + 5 ;int n, m;vector<pair<int , int >> E[N]; bool vis[N];int dis[N];bool Bellman_Ford (int u) { vis[u] = true ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (vis[v] || Bellman_Ford (v)) return true ; } } vis[u] = false ; return false ; } int T;int main () { scanf ("%d" , &T); while (T--) { for (int u = 1 ; u <= n; u++) E[u].clear (); memset (vis, false , sizeof (vis)); memset (dis, 0x3f , sizeof (dis)); scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, w)); if (w >= 0 ) E[v].push_back (make_pair (u, w)); } dis[1 ] = 0 ; puts (Bellman_Ford (1 ) ? "YES" : "NO" ); } return 0 ; }
在队列优化中,可以用一个点的入队次数是否 大于等于 n n n 进行判断
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <bits/stdc++.h> using namespace std;const int N = 10000 + 5 ;int n, m;vector<pair<int , int >> E[N]; bool vis[N];queue<int > Q; int dis[N], cnt[N];bool SPFA (int s) { memset (vis, false , sizeof (vis)); memset (dis, 0x3f , sizeof (dis)); memset (cnt, 0 , sizeof (cnt)); dis[s] = 0 ; vis[s] = true ; cnt[s] = 1 ; Q.push (s); while (!Q.empty ()) { int u = Q.front (); Q.pop (); vis[u] = false ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (vis[v]) continue ; vis[v] = true ; Q.push (v); ++cnt[v]; if (cnt[v] > n + 1 ) return true ; } } } return false ; } int T;int main () { scanf ("%d" , &T); while (T--) { for (int u = 1 ; u <= n; u++) E[u].clear (); scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, w)); if (w >= 0 ) E[v].push_back (make_pair (u, w)); } puts (SPFA (1 ) ? "YES" : "NO" ); } return 0 ; }
3.2.2 差分约束问题
例题
Luogu P1993 小 K 的农场
给出一组包含 m m m 个不等式,有 n n n 个未知数的不等式组(不等式的形式可能为 a − b ≤ c , a − b ≥ c , a − b = c a - b \leq c, a - b \geq c, a - b = c a − b ≤ c , a − b ≥ c , a − b = c ),求任意一组满足这个不等式组的解。
题解
此类问题可以将 x u − x v ≤ y x_u - x_v \leq y x u − x v ≤ y 转化为 x u ≤ x v + y x_u \leq x_v + y x u ≤ x v + y ,对应到三角形不等式中就是 d i s v ≤ d i s u + w dis_v \leq dis_u + w d i s v ≤ d i s u + w ,因此,只要在图中对每一组 u → v u \to v u → v 建一条边权为 y y y 的边即可。
同理,若不等式为 x u − x v ≥ y x_u - x_v \geq y x u − x v ≥ y ,可以将其转化为 x v − x u ≤ − y x_v - x_u \leq -y x v − x u ≤ − y 处理
若出现了 x u − x v = y x_u - x_v = y x u − x v = y ,可以将其转化为 x u − x v ≤ y x_u - x_v \leq y x u − x v ≤ y 和 x u − x v ≥ y x_u - x_v \geq y x u − x v ≥ y 处理
新建一个虚拟节点 O O O ,由该节点往其他所有点连一条边权为 0 0 0 的边,使用队列优化的 Bellman-Ford 算法求出从 O O O 点到其他所有点的最短路即为方程的一个解.
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 #include <bits/stdc++.h> using namespace std;const int N = 10000 + 5 ;int n, m;vector<pair<int , int >> E[N]; bool vis[N];queue<int > Q; int dis[N], cnt[N];bool SPFA (int s) { memset (vis, false , sizeof (vis)); memset (dis, 0x3f , sizeof (dis)); memset (cnt, 0 , sizeof (cnt)); dis[s] = 0 ; vis[s] = true ; cnt[s] = 1 ; Q.push (s); while (!Q.empty ()) { int u = Q.front (); Q.pop (); vis[u] = false ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (vis[v]) continue ; vis[v] = true ; Q.push (v); ++cnt[v]; if (cnt[v] > n + 1 ) return true ; } } } return false ; } int main () { scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= m; i++) { int op, u, v, w; scanf ("%d" , &op); if (op == 1 ) { scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, -w)); } else if (op == 2 ) { scanf ("%d%d%d" , &u, &v, &w); E[v].push_back (make_pair (u, w)); } else { scanf ("%d%d" , &u, &v); E[v].push_back (make_pair (u, 0 )); E[u].push_back (make_pair (v, 0 )); } } for (int i = 1 ; i <= n; i++) E[0 ].push_back (make_pair (i, 0 )); puts (SPFA (0 ) ? "No" : "Yes" ); return 0 ; }
4 Johnson - 全源最短路
4.1 原理
Luogu P5905【模板】全源最短路(Johnson)
其实就是跑 n n n 遍 D i j k s t r a Dijkstra D i j k s t r a
由于原图可能存在负边权,所以我们还需要做些处理
新建一个虚拟节点 O O O ,由该节点往其他所有点连一条边权为 0 0 0 的边,使用 Bellman-Ford 算法求出从 O O O 点到其他所有点的最短路 h i h_i h i .
接下来我们对每一条 u → v u \to v u → v 的路径,将其边权 w w w 重新设置为 w + h u − h v w + h_u - h_v w + h u − h v .
然后以每个点为起点,跑 n n n 轮 D i j k s t r a Dijkstra D i j k s t r a 算法即可求出全源最短路.
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 #include <bits/stdc++.h> using namespace std;const int N = 3000 + 5 ;vector<pair<int , int >> E[N]; bool vis[N];int h[N], cnt[N];bool SPFA (int n, int s) { queue<int > Q; memset (h, 0x3f , sizeof (h)); h[s] = 0 ; vis[s] = true ; Q.push (s); while (!Q.empty ()) { int u = Q.front (); Q.pop (); vis[u] = false ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (h[v] > h[u] + w) { h[v] = h[u] + w; if (vis[v]) continue ; vis[v] = true ; Q.push (v); ++cnt[v]; if (cnt[v] == n + 1 ) return false ; } } } return true ; } int dis[N];inline void Dijkstra (int n, int s) { priority_queue<pair<int , int >, vector<pair<int , int >>, greater<pair<int , int >>> Q; memset (dis, 0x3f , sizeof (dis)); memset (vis, false , sizeof (vis)); dis[s] = 0 ; Q.push (make_pair (0 , s)); while (!Q.empty ()) { int u = Q.top ().second; Q.pop (); if (vis[u]) continue ; vis[u] = true ; for (auto nxt : E[u]) { int v = nxt.first, w = nxt.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) Q.push (make_pair (dis[v], v)); } } } } int n, m;int main () { scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= m; i++) { int u, v, w; scanf ("%d%d%d" , &u, &v, &w); E[u].push_back (make_pair (v, w)); } for (int i = 1 ; i <= n; i++) E[0 ].push_back (make_pair (i, 0 )); if (!SPFA (n, 0 )) { puts ("-1" ); return 0 ; } for (int u = 1 ; u <= n; u++) for (auto &nxt : E[u]) nxt.second += h[u] - h[nxt.first]; for (int i = 1 ; i <= n; i++) { Dijkstra (n, i); long long ans = 0 ; for (int j = 1 ; j <= n; j++) { if (dis[j] == 0x3f3f3f3f ) ans += 1LL * j * 1000000000 ; else ans += 1LL * j * (dis[j] - h[i] + h[j]); } printf ("%lld\n" , ans); } return 0 ; }
4.2 应用
几乎没有应用…
5 总结
算法
Floyd-Warshall
Dijkstra
Bellman-Ford
Johnson
空间复杂度
O ( N 2 ) O(N^2) O ( N 2 )
O ( M ) O(M) O ( M ) (优先队列优化) O ( N ) O(N) O ( N ) (配对堆优化)
O ( M ) O(M) O ( M )
O ( M ) O(M) O ( M )
时间复杂度
O ( N 3 ) O(N^3) O ( N 3 )
O ( N × M ) O(N \times M) O ( N × M ) O ( ( N + M ) l o g M ) O((N + M) log M) O ( ( N + M ) l o g M ) (优先队列优化) O ( ( N + M ) l o g N ) O((N + M) log N) O ( ( N + M ) l o g N ) (配对堆优化)
O ( N × M ) O(N \times M) O ( N × M ) O ( k × N ) ( 1 ≤ k ≤ M ) O(k \times N) (1 \leq k \leq M) O ( k × N ) ( 1 ≤ k ≤ M ) (队列优化)
O ( N × M l o g M ) O(N \times M logM) O ( N × M l o g M )
适用情况
稠密图 和顶点关系密切
稠密图 和顶点关系密切
稀疏图 和边关系密切
稀疏图 和边关系密切
负权
可以解决负权
不能解决负权
可以解决负权
可以解决负权