Acwing算法基础课学习笔记(八)--搜索与图论之最短路问题-Dijkstra&&bellman-ford&&spfa&&Floyd_h[n], e[n], ne[n], idx

最短路问题是一个比较大的问题，我们将花一节课的时间来介绍，这一节的内容其实也不算难，只是需要记忆的内容比较多，本节课所讲的几个模板都需要背熟练！代码就是要多写，形成肌肉记忆！一般来说，在做算法题的时候，抽象出图论的知识是比较容易的，小学数奥难度，核心还是在于算法实现，所以一定要多写！

图论问题的难点在于如何建图。

Dijkstra求最短路 I

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int n, m;
int g[N][N];//稠密图一般使用邻接矩阵
int dist[N];//记录每个节点距离起点的距离
bool st[N];//True表示已经确定最短路 属于s集合

int dijkstra()
{
	memset(dist, 0x3f, sizeof dist);//所有节点距离起点的距离初始化为无穷大
	dist[1] = 0; //起点距离自己的距离为零
	for (int i = 0; i < n; i++) // 迭代n次，每次可以确定一个点到起点的最短路
	{
		int t = -1;
		for (int j = 1; j <= n; j++)
			//不在s集合，并且如果没有更新过，则进行更新， 或者发现更短的路径，则进行更新
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		if (t == n)	break;

		st[t] = true;//加入到s集合中

		for (int j = 1; j <= n; j++)//找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
			dist[j] = min(dist[j], dist[t] + g[t][j]);
	}

	if (0x3f3f3f3f == dist[n])	return -1;// 如果起点到达不了n号节点，则返回-1
	return dist[n]; //返回起点距离n号节点的最短距离

}
int main()
{
	scanf("%d%d", &n, &m);
	memset(g, 0x3f, sizeof g);//所有节点之间的距离初始化为无穷大

	while (m--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c);//如果有重边，请保留权值最小的一条边
	}

	int t = dijkstra();
	printf("%d\n", t);

	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

int t = -1;
//t的作用？
一开始t的赋值是-1
如果t没有被更新，
那么要更新一下t
其实t等于负多少都没事，因为在第一次 st[j] 成功时 就会直接将现在的 j 赋值给 t 。因此 t 只是起到一个 在前面的最短路径点集合确定好后 ，在开启新的一轮寻找最近点时，用来标记在该轮中是否已经心找到一个 (目前来说)最短点的作用。

// 0x3f 0x3f3f3f3f 的区别？
memset 按字节赋值，所以memset 0x3f 就等价与赋值为0x3f3f3f3f

Dijkstra求最短路 II

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c; // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    e[idx] = y; // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），并
    ne[idx] = h[x]; // 标记st为true，所以下一次弹出3+x会continue不会向下执行。
    h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 1;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，其次在从堆中拿出来的时    
    // 候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    while (heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if (0x3f3f3f3f == dist[n]) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    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
68
69
70
71
72
73

有边数限制的最短路

推荐题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;
int n, m, k;
int dist[N];//距离
int backup[N];//备份数组放置串联

struct Edge
{
	int a, b, w;
}edges[M];//把每个边保存下来即可

int bellman_ford()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;

	for (int i = 0; i < k; i++)//k次循环
	{
		memcpy(backup, dist, sizeof dist);
		for (int j = 0; j < m; j++)//遍历所有边
		{
			int a = edges[j].a, b = edges[j].b, w = edges[j].w;
			dist[b] = min(dist[b], backup[a] + w);//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
		}
	}

	if (dist[n] > 0x3f3f3f3f / 2)	return -1;
	return dist[n];
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = { a, b, w };
	}

	int t = bellman_ford();
	if (-1 == t)	puts("impossible");
	else printf("%d\n", t);
	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

Bellman_ford算法一般没有spfa算法优，一般来说，只有存在最多经过k条边这个限制的时候，才会使用Bellman_ford 算法，其他存在负权边的情况下，我们都会使用下面的SPFA算法。

spfa求最短路

spfa是限制最少的一种最短路算法，也是对Bellman_ford算法的优化，只要图中没有负环即可，99.9%的最短路问题是没有负环的。可见spfa的强大之处。不过也有spfa算法已死的说法，都是坏得很的出题人的恶意（逃
如果被卡的话，就要换成堆优化版的dijsktra算法去做。

推荐题解

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())//队列不空
    {
        int t = q.front();//取出队头
        q.pop(); //删去队头
        //从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])//更新t的所有邻边
        {
            int j = e[i];//当前点
            if (dist[j] > dist[t] + w[i])//看看是否能够更新
            {
                dist[j] = dist[t] + w[i];//能更新
                if (!st[j])//当前已经加入队列的结点，无需再次加入队列，j不在队列里才需要加入队列
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (0x3f3f3f == dist[n])	return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();

    if (0x3f3f3f3f == t) puts("impossible");
    else printf("%d\n", t);

    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
68
69
70
71
72
73
74

spfa判断负环

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
int cnt[N];//cnt数组表示到达当前这个点最短路的边数
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i++)//判整个图的负环要将每个节点都加入
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())//队列不空
    {
        int t = q.front();//取出队头
        q.pop(); //删去队头
        //从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])//更新t的所有邻边
        {
            int j = e[i];//当前点
            if (dist[j] > dist[t] + w[i])//看看是否能够更新
            {
                dist[j] = dist[t] + w[i];//能更新

                cnt[j] = cnt[t] + 1;
                //经过n条边则经过了n+1个点，根据抽屉原理，说明经过某个点两次，则说明有环
                if (cnt[j] >= n) return true;

                if (!st[j])//当前已经加入队列的结点，无需再次加入队列，j不在队列里才需要加入队列
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else printf("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
68
69
70
71
72
73
74
75
76
77
78

Floyd求最短路

Floyd超简单，用来解决多源汇最短路问题，原理基于动态规划。经过三重循环就可以把邻接矩阵变成所要求的最短路。

d[k, i, j] = d[k - 1, i, k] + d[k - 1, k, i]
1

由于k不影响最后结果，因此可以去掉，所以最终的转移方程就是：

d[i, j] = d[i, k] + d[k, j]
1

完整代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];

void floyd()
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
	scanf("%d%d%d", &n, &m, &Q);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i == j)	d[i][i] == 0;//自己到自己的距离是0
			else d[i][j] = INF;

	while (m--)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		d[a][b] = min(d[a][b], w);//有多条边的话只保留最小的边
	}

	floyd();

	while (Q--)
	{
		int a, b;
		scanf("%d%d", &a, &b);

		int t = d[a][b];
		if (t > INF / 2) puts("impossible");
		else printf("%d\n", t);
	}

	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

本章总结：

Dijkstra-朴素O(n^2)

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

Dijkstra-堆优化O(mlogm)

 1. 利用邻接表，优先队列
 2. 在priority_queue[HTML_REMOVED], greater[HTML_REMOVED] > heap;中将返回堆顶
 3. 利用堆顶来更新其他点，并加入堆中类似宽搜
1
2
3

Bellman_fordO(nm)

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

Spfa O(n)~O(nm)

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

Floyd O(n^3)

 1. 初始化d
 2. k, i, j 去更新d。
1
2