最短路径算法

Hervey Lv3
  2024-02-06 07:31:54 2024-02-06 07:31:54 创建   2025-03-02 14:22:34 2025-03-02 14:22:34 更新      

0 前言

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

1 Floyd-Warshall - 多源最短路

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

1.1 原理

AcWing 854. Floyd求最短路

设 表示点 到点 的最短路径，枚举中转点 ，每次通过中转点更新最短路径，转移方程 Missing or unrecognized delimiter for \leftF_{i,j} = min\left{ G_{i,j}, F_{i,k} + F_{k,j} \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
#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 【模板】传递闭包

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

一张图的邻接矩阵定义为一个 的矩阵 ，其中

$$
a_{ij}=\left{
到存在直接连边到没有直接连边
\right.
$$

一张图的传递闭包定义为一个 的矩阵 ，其中

$$
b_{ij}=\left{
可以直接或间接到达无法直接或间接到达
\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
#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 跳楼机

给定 ，对于 ，求有多少个 能够满足 .

题解

设 为满足 的最小 ，这里记为 .

可以得到两个转移方程:

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

这样，即可获得答案 

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

对所有的边进行 次 松弛 操作

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【模板】负环

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

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

题解

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

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

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

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

给出一组包含 个不等式，有 个未知数的不等式组(不等式的形式可能为 )，求任意一组满足这个不等式组的解。

题解

此类问题可以将 转化为 ，对应到三角形不等式中就是 ，因此，只要在图中对每一组 建一条边权为 的边即可。

同理，若不等式为 ，可以将其转化为 处理

若出现了 ，可以将其转化为 和 处理

新建一个虚拟节点 ，由该节点往其他所有点连一条边权为 的边，使用队列优化的 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
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）

其实就是跑 遍

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

新建一个虚拟节点 ，由该节点往其他所有点连一条边权为 的边，使用 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
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
空间复杂度 (优先队列优化)
(配对堆优化)
时间复杂度
(优先队列优化)
(配对堆优化)
(队列优化)
适用情况 稠密图
和顶点关系密切		 稠密图
和顶点关系密切		 稀疏图
和边关系密切		 稀疏图
和边关系密切
负权 可以解决负权 不能解决负权 可以解决负权 可以解决负权
  • 标题: 最短路径算法
  • 作者: Hervey
  • 创建于 : 2024-02-06 07:31:54
  • 更新于 : 2025-03-02 14:22:34
  • 链接: https://herveyb3b4.github.io/2024/02/06/Alogrithm/Notes/Shortest-Path/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
最短路径算法
  1. 0 前言
  2. 1 Floyd-Warshall - 多源最短路
    1. 1.1 原理
    2. 1.2 应用
  3. 2 Dijkstra - 单源最短路
    1. 2.1 原理及优化
    2. 2.2 应用
  4. 3 Bellman-Ford - 单源最短路
    1. 3.1 原理及优化
    2. 3.2 应用
  5. 4 Johnson - 全源最短路
    1. 4.1 原理
    2. 4.2 应用
  6. 5 总结