最短路#

我们学编程不会让我们去数学证明，我们只需要知道结论，然后用代码去“实现”就好了，实际上就比的是记忆能力。

算法速览#

分类（在每种情况下，都有各自的最优抉择）

单源最短路（求一个点到其他所有点的最短距离）
- 所有边权重为正数
  - 朴素Dijkstra： $O(n^2)$ ，适合稠密图
  - 堆优化Dijkstra： $O(m\log n)$ ，适合稀疏图
- 存在负权边
  - Bellman-Ford： $O(nm)$ ，可限制边数，无负权回路才有解
  - SPFA：平均 $O(m)$ ，最坏 $O(nm)$ ，队列优化的 Bellman-Ford
多源汇最短路（任意两点之间最短距离）
- Floyd： $O(n^3)$

所有算法默认针对有向图。无向图等价于双向有向边。

朴素 Dijkstra#

题目：AcWing 849. Dijkstra求最短路 I
链接：https://www.acwing.com/problem/content/851/

完整题面#

题目描述#

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式#

第一行包含两个整数 n 和 m。接下来 m 行，每行包含三个整数 a,b,c，表示存在一条从 a 走到 b 的有向边，边长为 c。

输出格式#

输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 −1。

数据范围#

$1≤n≤500$
$1≤m≤10^5$
$1≤a,b≤n$
$c>0$

输入样例#

输出样例#

1
3

代码（含完整思考注释）#

1
#include <iostream>
2
#include <algorithm>
3
#include <cstring>
4

5
using namespace std;
6

7
const int N = 510; // 这是一个稠密图，所以用邻接矩阵来存
8

9
int n, m;    // n个点，m条边
10
int g[N][N]; // 邻接矩阵
11
int dist[N]; // 距离数组：dist[i]表示1号点到i号点的最短距离
12
bool st[N];  // st[i]表示i号点是否已经确定了距离
13

14
int dijkstra()
15
{
16
    // 为什么要用0x3f，
17
    // 因为memset是针对每个字节进行操作的，
18
    // C++中int型变量所占的位数为4个字节，即32位
19
    // 4个字节均为0x3f时，0x3f3f3f3f的十进制是1061109567，也就是10^9级别的（和0x7fffffff一个数量级）
20
    memset(dist, 0x3f, sizeof dist); // 初始化距离数组，把所有点的距离都设置为正无穷
21
    dist[1] = 0;                     // 把起点的距离设置为0
22

23
    for (int i = 0; i < n - 1; i++) // 迭代n - 1次
24
    {
25
        int t = -1; // 找到不在s中的，距离最近的点t
26
        for (int j = 1; j <= n; j++)
27
            // 下面这个 if 的意思就是：在不在s中的点中（距离还没有确定距离，即st[j]为false的第一个点），找到距离最近的点t
28
            if (!st[j] && (t == -1 || dist[t] > dist[j])) // 如果j不在s中，并且t是第一个点，或者dist[t] > dist[j]
29
                t = j;                                    // 那么就把j赋值给t
30

31
        // // 可以选加的优化
32
        // if (t == n) break; // 如果t == n，说明1号点到n号点的最短距离已经确定了，所以就可以退出循环
33

34
        st[t] = true; // 把t加入s
35

36
        for (int j = 1; j <= n; j++)                   // 用t更新其他点的距离
37
            dist[j] = min(dist[j], dist[t] + g[t][j]); // dist[j] = min(dist[j], dist[t] + g[t][j])
38
        // 为什么是min呢？
39
        // 因为我们是要找到1号点到n号点的最短距离，所以我们要取最小值
40
    }
41

42
    if (dist[n] == 0x3f3f3f3f)
43
        return -1;  // 如果dist[n] == 0x3f3f3f3f，说明1号点到n号点没有路径，返回-1
44

45
    return dist[n]; // 返回1号点到n号点的最短距离
46
}
47

48
int main()
49
{
50
    scanf("%d%d", &n, &m);
51

52
    memset(g, 0x3f, sizeof g); // 初始化邻接矩阵，把所有边的权重都设置为正无穷
53

54
    while (m--)
55
    {
56
        int a, b, c;
57
        scanf("%d%d%d", &a, &b, &c);
58
        g[a][b] = min(g[a][b], c); // 因为可能存在重边，所以要取最小值
59
    }
60

61
    int t = dijkstra();
62

63
    printf("%d\n", t);
64

65
    return 0;
66
}
67

68
// 如果想优化时间复杂度，可以使用堆优化
69
// 用堆优化的方式有2种：
70
//  1.手写堆
71
//  2.使用STL中的priority_queue（优先队列）
72

73
// 因为优先队列比手写堆要简单，所以我们一般使用优先队列来优化
74
// 具体优化方法见下一节

堆优化 Dijkstra#

题目：AcWing 850. Dijkstra求最短路 II
链接：https://www.acwing.com/problem/content/852/

完整题面#

题目描述#

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式#

第一行包含两个整数 n 和 m。接下来 m 行，每行包含三个整数 a,b,c，表示存在一条从 a 走到 b 的有向边，边长为 c。

输出格式#

输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 −1。

数据范围#

$1≤n,m≤1.5×10^5$
$1≤a,b≤n$
$c≥0$

输入样例#

输出样例#

1
3

代码#

1
#include <iostream>
2
#include <algorithm>
3
#include <cstring>
4
#include <queue>
5

6
using namespace std;
7

8
typedef pair<int, int> PII; // 定义一个pair类型，第一个元素是距离，第二个元素是点的编号
9

10
const int N = 100010;
11

12
int n, m; // n个点，m条边
13
int h[N], e[N], ne[N], w[N], idx; // h是邻接表的头结点，e是边的终点，ne是下一条边的编号，w是边的权重，idx是边的编号
14
int dist[N]; // 存储1号点到每个点的最短距离
15
bool st[N]; // 存储每个点是否已经确定了距离
16

17
void add(int a, int b, int c) // 添加一条边a->b，权重为c
18
{
19

20
    // 这样子想：h[a]是一个链表，链表的头结点是h[a]，头结点的下一个是起点结点是ne[idx]，即ne[h[a]]，头结点的下一个的下一个结点是ne[ne[h[a]]]，以此类推
21
    // 其中e[idx]是起点对应的终点，w[idx]是权重，可以看成起点的2个内容元素。
22
    e[idx] = b;
23
    // cout << "e[" << idx << "] = " << b << endl;
24
    w[idx] = c;
25
    // cout << "w[" << idx << "] = " << c << endl;
26
    ne[idx] = h[a];
27
    // cout << "ne[" << idx << "] = " << h[a] << endl;
28
    h[a] = idx;
29
    // cout << "h[" << a << "] = " << idx << endl;
30
    idx++;
31
    // cout << "idx = " << idx << endl;
32
}
33

34
int dijkstra()
35
{
36
    memset(dist, 0x3f, sizeof dist);
37
    dist[1] = 0;
38

39
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆，存储距离和点的编号
40
    heap.push({0, 1}); // 把距离为0的1号点加入堆中
41

42
    while (heap.size())// while堆不为空
43
    {
44
        auto t = heap.top(); // 每次找到距离最小的点，也就是堆顶元素
45
        heap.pop(); // 弹出堆顶元素
46

47
        int ver = t.second, distance = t.first; // ver是点的编号，distance是距离
48

49
        if (st[ver]) continue; // 如果这个点已经被确定了距离，就跳过
50
        // 比如有2条路被记录到堆中，一条是{4, 3}，{5, 3}，前者是{ 距离为4 , 起点到点3 }，后者是{ 距离为5 , 起点到点3}
51
        // 由于小根堆的特性，{4, 3}会被先取出，这是一切正常运行，st[3]会从false标记成true，然后堆里剩下的那个{5, 3}就没有了意义，等到{5, 4}时就会直接continue
52
        st[ver] = true;
53

54
        for (int i = h[ver]; i != -1; i = ne[i]) // 遍历ver的所有出边
55
        {
56
            int j = e[i]; // j是ver的出边的终点
57
            if (dist[j] > distance + w[i]) // 如果j的距离大于ver的距离加上ver到j的权重
58
            {
59
                dist[j] = distance + w[i]; // 更新j的距离
60
                heap.push({dist[j], j}); // 把j加入堆中
61
            }
62
        }
63
    }
64

65

66
    if (dist[n] == 0x3f3f3f3f) return -1;  // 如果dist[n] == 0x3f3f3f3f，说明1号点到n号点没有路径，返回-1
67

68
    return dist[n]; // 返回1号点到n号点的最短距离
69
}
70

71
int main()
72
{
73
    scanf("%d%d", &n, &m);
74

75
    memset(h, -1, sizeof h); // 初始化邻接表
76

77
    while (m--)
78
    {
79
        int a, b, c;
80
        scanf("%d%d%d", &a, &b, &c);
81
        add(a, b, c); // 添加一条边a->b，权重为c
82
    }
83

84
    int t = dijkstra();
85

86
    printf("%d\n", t);
87

88
    return 0;
89
}

Bellman-Ford#

题目：AcWing 853. 有边数限制的最短路
链接：https://www.acwing.com/problem/content/855/

完整题面#

题目描述#

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

输入格式#

第一行包含三个整数 n,m,k。接下来 m 行，每行包含三个整数 a,b,c，表示存在一条从 a 走到 b 的有向边，边长为 c。

输出格式#

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。如果不存在满足条件的路径，则输出 impossible。

数据范围#

$1≤n,k≤500$
$1≤m≤10^4$
$1≤a,b≤n$
$−10^4≤c≤10^4$

输入样例#

输出样例#

1
3

代码#

1
#include<iostream>
2
#include<iostream>
3
#include<algorithm>
4
#include<cstring>
5
using namespace std;
6

7
const int N = 510, M = 10010;
8

9
int n, m, k;
10
int dist[N], backup[N];
11

12
struct Edge
13
{
14
    int a, b, w;
15
}edges[M]; // 这里edges[M]是一个数组，数组的元素是Edge类型的结构体
16

17
int bellman_ford()
18
{
19
    memset(dist, 0x3f, sizeof dist); // 初始化dist数组
20
    dist[1] = 0; // 1号点到1号点的距离为0
21

22
    for(int i = 0; i < k; i++)
23
    {
24
        memcpy(backup, dist, sizeof dist); // 备份dist数组
25
        // 为什么要备份dist数组？
26
        // 因为我们要更新dist数组，但是我们要保证更新dist数组的时候，dist数组中的值是上一次迭代的结果，而不是本次迭代的结果
27
        for(int j = 0; j < m; j++)
28
        {
29
            int a  = edges[j].a, b = edges[j].b, w = edges[j].w;
30
            dist[b] = min(dist[b], backup[a] + w); // 更新dist数组
31
        }
32
    }
33

34
    if(dist[n] > 0x3f3f3f3f / 2) return -1; // 如果dist[n]大于(一个量级很大的数) 0x3f3f3f3f / 2，说明最短路不存在
35
    return dist[n]; // 否则，返回dist[n]
36

37
}
38

39
int main()
40
{
41
    scanf("%d%d%d", &n, &m, &k);
42

43
    for(int i = 0; i < m; i++)
44
    {
45
        int a, b, w;
46
        scanf("%d%d%d", &a, &b, &w);
47
        edges[i] = {a, b, w};
48
    }
49

50
    int t = bellman_ford();
51

52
    if(t == -1) puts("impossible"); // 如果最短路不存在，输出impossible
53
    else printf("%d\n", t); // 否则，输出最短距离
54

55
    return 0;
56
}

SPFA 求最短路#

题目：AcWing 851. spfa求最短路
链接：https://www.acwing.com/problem/content/853/

完整题面#

题目描述#

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

输入格式#

第一行包含两个整数 n 和 m。接下来 m 行，每行包含三个整数 a,b,c，表示存在一条从 a 走到 b 的有向边，边长为 c。

输出格式#

输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 impossible。

数据范围#

$1≤n,m≤10^5$
$1≤a,b≤n$
$−10^9≤c≤10^9$

输入样例#

输出样例#

1
2

代码#

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
#include<queue>
5

6
using namespace std;
7

8
const int N = 100010;
9

10
int n, m;
11
int h[N], e[N], ne[N], w[N], idx;
12
int dist[N];
13
bool st[N];
14

15
void add(int a, int b, int c)
16
{
17
    w[idx] = c;
18
    e[idx] = b;
19
    ne[idx] = h[a];
20
    h[a] = idx;
21
    // 这样子想：h[a]是一个链表，链表的头结点是h[a]，头结点的下一个是起点结点是ne[idx]，即ne[h[a]]，头结点的下一个的下一个是起点结点是ne[ne[h[a]]]，以此类推
22
    // 其中e[idx]是起点对应的终点，w[idx]是权重，可以看成起点的2个内容元素。
23
    idx ++;
24
}
25

26
int spfa()
27
{
28
    memset(dist, 0x3f, sizeof dist);
29
    dist[1] = 0;
30

31
    queue<int> q;
32
    q.push(1); // 把距离为0的1号点加入队列中
33
    st[1] = true; // 表示1号点在队列中
34

35
    while(q.size())
36
    {
37
        int t = q.front();
38
        q.pop();
39

40
        st[t] = false; // 表示t号点不在队列中
41

42
        for(int i = h[t]; i != -1; i = ne[i]) // 更新t号点的所有出边
43
        {
44
            int j = e[i];
45
            if(dist[j] > dist[t] + w[i]) // 如果j号点的距离大于t号点的距离加上边权
46
            {
47
                dist[j] = dist[t] + w[i]; // 更新j号点的距离
48
                if(!st[j]) // 如果j号点不在队列中
49
                {
50
                    q.push(j); // 把j号点加入队列中
51
                    st[j] = true; // 表示j号点在队列中
52
                }
53
            }
54
        }
55
    }
56

57
    if(dist[n] == 0x3f3f3f3f) return -1;
58
    return dist[n];
59
}
60

61
int main()
62
{
63
    cin >> n >> m;
64

65
    memset(h, -1, sizeof h);
66

67
    while(m--)
68
    {
69
        int a, b, c;
70
        cin >> a >> b >> c;
71
        add(a, b, c);
72
    }
73

74
    int t = spfa();
75

76
    if(t == -1) cout << "impossible" << endl;
77
    else cout << t << endl;
78

79
    return 0;
80
}

SPFA 判断负环#

题目：AcWing 852. spfa判断负环
链接：https://www.acwing.com/problem/content/854/

完整题面#

题目描述#

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路。

输入格式#

第一行包含两个整数 n 和 m。接下来 m 行，每行包含三个整数 a,b,c，表示存在一条从 a 走到 b 的有向边，边长为 c。

输出格式#

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围#

$1≤n≤2000$
$1≤m≤10^4$
$1≤a,b≤n$
$−10^4≤c≤10^4$

输入样例#

输出样例#

1
Yes

代码#

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4
#include<queue>
5

6
using namespace std;
7

8
const int N = 100010;
9

10
int n, m;
11
int h[N], e[N], ne[N], w[N], idx;
12
int dist[N], cnt[N];
13
bool st[N];
14

15
void add(int a, int b, int c)
16
{
17
    w[idx] = c;
18
    e[idx] = b;
19
    ne[idx] = h[a];
20
    h[a] = idx;
21
    // 这样子想：h[a]是一个链表，链表的头结点是h[a]，头结点的下一个是起点结点是ne[idx]，即ne[h[a]]，头结点的下一个的下一个是起点结点是ne[ne[h[a]]]，以此类推
22
    // 其中e[idx]是起点对应的终点，w[idx]是权重，可以看成起点的2个内容元素。
23
    idx ++;
24
}
25

26
bool spfa()
27
{
28
    queue<int> q;
29
    for(int i = 1; i <= n; i++) // 我们一开始需要把所有点都加入队列中，然后从每个点开始判断是否有负环
30
    {
31
        q.push(i);
32
        st[i] = true;
33
    }
34

35
    while(q.size())
36
    {
37
        int t = q.front();
38
        q.pop();
39

40
        st[t] = false; // 表示t号点不在队列中
41

42
        for(int i = h[t]; i != -1; i = ne[i]) // 更新t号点的所有出边
43
        {
44
            int j = e[i];
45
            if(dist[j] > dist[t] + w[i]) // 如果j号点的距离大于t号点的距离加上边权
46
            {
47
                dist[j] = dist[t] + w[i]; // 更新j号点的距离
48
                cnt[j] = cnt[t] + 1; // 更新j号点的入队次数
49

50
                if(cnt[j] >= n) return true; // 如果j号点的入队次数大于等于n，则说明存在负环
51

52
                if(!st[j]) // 如果j号点不在队列中
53
                {
54
                    q.push(j); // 把j号点加入队列中
55
                    st[j] = true; // 表示j号点在队列中
56
                }
57
            }
58
        }
59
    }
60

61
    return false;
62
}
63

64
int main()
65
{
66
    cin >> n >> m;
67

68
    memset(h, -1, sizeof h);
69

70
    while(m--)
71
    {
72
        int a, b, c;
73
        cin >> a >> b >> c;
74
        add(a, b, c);
75
    }
76

77
    if(spfa()) puts("Yes");
78
    else puts("No");
79

80
    return 0;
81
}

Floyd 多源最短路#

题目：AcWing 854. Floyd求最短路
链接：https://www.acwing.com/problem/content/856/

完整题面#

题目描述#

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定 k 个询问，每个询问包含两个整数 x 和 y，表示求从点 x 到点 y 的最短距离。如果路径不存在，则输出 impossible。

输入格式#

第一行包含三个整数 n,m,k。接下来 m 行，每行包含三个整数 a,b,c，表示存在一条从 a 走到 b 的有向边，边长为 c。接下来 k 行，每行包含两个整数 x,y，表示询问从点 x 到点 y 的最短距离。

输出格式#

共 k 行，每行输出一个整数，表示询问的结果。如果路径不存在，则输出 impossible。

数据范围#

$1≤n≤200$
$1≤m≤20000$
$1≤k≤10^4$
$1≤a,b,x,y≤n$
$−10^9≤c≤10^9$

输入样例#

输出样例#

1
impossible
2
1

代码#

1
#include<iostream>
2
#include<algorithm>
3
#include<cstring>
4

5
using namespace std;
6

7
const int N = 210, INF = 1e9;
8

9
int n, m, Q; // n个点，m条边，Q个询问
10
int d[N][N]; // d是邻接矩阵，d[i][j]表示从i到j的最短距离
11

12
void floyd()
13
{
14
    for(int k = 1; k <= n; k++) // 枚举中间点
15
        for(int i = 1; i <= n; i++) // 枚举起点
16
            for(int j = 1; j <= n; j++) // 枚举终点
17
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // 松弛操作
18
}
19

20
int main()
21
{
22
    scanf("%d%d%d", &n, &m, &Q);
23

24
    // 初始化邻接矩阵，将所有点到自己的距离初始化为0，其他点到自己的距离初始化为无穷大
25
    for(int i = 1; i <= n; i++)
26
        for(int j = 1; j <= n; j++)
27
            if(i == j) d[i][j] = 0;
28
            else d[i][j] = INF;
29

30
    while(m--)
31
    {
32
        int a, b, w;
33
        scanf("%d%d%d", &a, &b, &w);
34

35
        d[a][b] = min(d[a][b], w); // 有重边，只保留最短的边
36
    }
37

38
    floyd();
39

40
    // 处理询问
41
    while(Q--)
42
    {
43
        int a, b;
44
        scanf("%d%d", &a, &b);
45

46
        if(d[a][b] > INF / 2) puts("impossible"); // 如果距离大于INF/2，说明没有路径
47
        else printf("%d\n", d[a][b]);
48
    }
49

50
    return 0;
51
}

总结#

Dijkstra-朴素 O(n^2)#

初始化距离数组, dist[1] = 0, dist[i] = inf;
for n次循环每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
将不在S中dist_min的点->t
t->S加入最短路集合
用t更新到其他点的距离

Dijkstra-堆优化 O(mlogm)#

利用邻接表，优先队列
在priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;中将返回堆顶
利用堆顶来更新其他点，并加入堆中类似宽搜的过程

Bellman_ford O(nm)#

注意连锁想象需要备份, struct Edge{int a,b,c} Edge[M];
初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
松弛k次，每次访问m条边

Spfa O(n)~O(nm)#

利用队列优化仅加入修改过的地方
for k次
for 所有边利用宽搜模型去优化bellman_ford算法
更新队列中当前点的所有出边

Floyd O(n^3)#

初始化d
k, i, j 去更新d

belgnasの站点

最短路#

算法速览#

朴素 Dijkstra#

完整题面#

题目描述#

输入格式#

输出格式#

数据范围#

输入样例#

输出样例#

代码（含完整思考注释）#

堆优化 Dijkstra#

完整题面#

题目描述#

输入格式#

输出格式#

数据范围#

输入样例#

输出样例#

代码#

Bellman-Ford#

完整题面#

题目描述#

输入格式#

输出格式#

数据范围#

输入样例#

输出样例#

代码#

SPFA 求最短路#

完整题面#

题目描述#

输入格式#

输出格式#

数据范围#

输入样例#

输出样例#

代码#

SPFA 判断负环#

完整题面#

题目描述#

输入格式#

输出格式#

数据范围#

输入样例#

输出样例#

代码#

Floyd 多源最短路#

完整题面#

题目描述#

输入格式#

输出格式#

数据范围#

输入样例#

输出样例#

代码#

总结#

Dijkstra-朴素 O(n^2)#

Dijkstra-堆优化 O(mlogm)#

Bellman_ford O(nm)#

Spfa O(n)~O(nm)#

Floyd O(n^3)#