最短路径算法

14k 词

0 前言

总结一些最短路问题的常用模板 (这回是小坑了)

1 Floyd-Warshall - 多源最短路

基础的动态规划,经典的三重循环,最简单的最短路算法

1.1 原理

AcWing 854. Floyd求最短路

Fi,jF_{i,j} 表示点 ii 到点 jj 的最短路径,枚举中转点 kk ,每次通过中转点更新最短路径,转移方程 Fi,j=min{Gi,j,Fi,k+Fk,j}F_{i,j} = min\left\{ G_{i,j}, F_{i,k} + F_{k,j} \right\} ,时间复杂度 O(N3)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);
// 可能出现负权边所以设置为INF/2
if (f[u][v] > INF / 2)
puts("impossible");
else
printf("%d\n", f[u][v]);
}
return 0;
}

1.2 应用

1.2.1 求图的传递闭包

例题

Luogu B3611 【模板】传递闭包

给定一张点数为 nn 的有向图的邻接矩阵,图中不包含自环,求该有向图的传递闭包。

一张图的邻接矩阵定义为一个 n×nn\times n 的矩阵 A=(aij)n×nA=(a_{ij})_{n\times n},其中

aij={1,i 到 j 存在直接连边0,i 到 j 没有直接连边a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边 \\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right.

一张图的传递闭包定义为一个 n×nn\times n 的矩阵 B=(bij)n×nB=(b_{ij})_{n\times n},其中

bij={1,i 可以直接或间接到达 j0,i 无法直接或间接到达 jb_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j \\ 0,i\ 无法直接或间接到达\ j \\ \end{aligned} \right.

题解

FloydFloyd 算法进行简单变形,记 fi,jf_{i,j} 表示 ii 可以直接或间接到达 jj

得到状态转移方程为 fi,j=k(fi,kfk,j)f_{i,j} = \lor_{k} (f_{i,k} \land 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),对于 k[1,h]k \in [1, h],求有多少个 kk 能够满足 ax+by+cz=kax+by+cz=k.

题解

did_i 为满足 (by+cz)1(mod x)(by+cz) \equiv 1 (mod \space x) 的最小 (by+cz)(by+cz) ,这里记为 pp.

可以得到两个转移方程:

  • di=d(i+y)mod x+yd_i = d_{(i + y) mod \space x} + y

  • di=d(i+z)mod x+zd_i = d_{(i + z) mod \space x} + z

类比三角形不等式,我们可以得到一个建图方案,进而通过单源最短路径算法求得 did_i .

这样,即可获得答案 i=0x1(hdix+1)\sum_{i=0}^{x - 1}\left(\frac{h - d_i}{x} + 1\right)

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 原理

对所有的边进行 n1n-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【模板】负环

给定一个 nn 个点的有向图,请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是:一条边权之和为负数的回路。

题解

若第 nn 轮迭代仍有结点的最短路能被更新,则说明图中存在负环

这里来个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;
}

在队列优化中,可以用一个点的入队次数是否 大于等于 nn 进行判断

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 的农场

给出一组包含 mm 个不等式,有 nn 个未知数的不等式组(不等式的形式可能为 abc,abc,ab=ca - b \leq c, a - b \geq c, a - b = c),求任意一组满足这个不等式组的解。

题解

此类问题可以将 xuxvyx_u - x_v \leq y 转化为 xuxv+yx_u \leq x_v + y ,对应到三角形不等式中就是 disvdisu+wdis_v \leq dis_u + w,因此,只要在图中对每一组 uvu \to v 建一条边权为 yy 的边即可。

同理,若不等式为 xuxvyx_u - x_v \geq y ,可以将其转化为 xvxuyx_v - x_u \leq -y 处理

若出现了 xuxv=yx_u - x_v = y ,可以将其转化为 xuxvyx_u - x_v \leq yxuxvyx_u - x_v \geq y 处理

新建一个虚拟节点 OO,由该节点往其他所有点连一条边权为 00 的边,使用队列优化的 Bellman-Ford 算法求出从 OO 点到其他所有点的最短路即为方程的一个解.

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);
// greater and equal
E[u].push_back(make_pair(v, -w));
}
else if (op == 2)
{
scanf("%d%d%d", &u, &v, &w);
// less and equal
E[v].push_back(make_pair(u, w));
}
else
{
scanf("%d%d", &u, &v);
// equal
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)

其实就是跑 nnDijkstraDijkstra

由于原图可能存在负边权,所以我们还需要做些处理

新建一个虚拟节点 OO,由该节点往其他所有点连一条边权为 00 的边,使用 Bellman-Ford 算法求出从 OO 点到其他所有点的最短路 hih_i.

接下来我们对每一条 uvu \to v 的路径,将其边权 ww 重新设置为 w+huhvw + h_u - h_v.

然后以每个点为起点,跑 nnDijkstraDijkstra 算法即可求出全源最短路.

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(N2)O(N^2) O(M)O(M)(优先队列优化)
O(N)O(N)(配对堆优化)
O(M)O(M) O(M)O(M)
时间复杂度 O(N3)O(N^3) O(N×M)O(N \times M)
O((N+M)logM)O((N + M) log M)(优先队列优化)
O((N+M)logN)O((N + M) log N)(配对堆优化)
O(N×M)O(N \times M)
O(k×N)(1kM)O(k \times N) (1 \leq k \leq M)(队列优化)
O(N×MlogM)O(N \times M logM)
适用情况 稠密图
和顶点关系密切
稠密图
和顶点关系密切
稀疏图
和边关系密切
稀疏图
和边关系密切
负权 可以解决负权 不能解决负权 可以解决负权 可以解决负权