0%

算法基础（8）

发表于 更新于 分类于 本文字数： 11k
最短路（Dijkstra，bellman-ford，spfa，Floyd）

常见的最短路问题：

  1. 单源最短路：求一个点到其他所有点的最短距离，如从1号点到N号点的最短路。又可分为：

    • 所有边的权重都是正数，一般有两种解法：

      • 朴素的Dijkstra算法（时间复杂度$O(n^2)）$，适合用于稠密图（$m$接近于$n^2$）；
      • 堆优化版的Dijkstra算法（时间复杂度$O(m \log n)$），适合用于稀疏图（$m$接近于$n$）；

      （设图中点的数量为$n$，边的数量为$m$）（稠密图用邻接矩阵来存，稀疏图用邻接表来存）

    • 存在权重是负数的边，一般也有两种解法：

      • Bellman-Ford算法（时间复杂度$O(nm)$）；
      • SPFA算法（一般情况下时间复杂度$O(m)$，最坏情况下$O(nm)$），但并不是所有情况都可用SPFA，如限制经过的边数不超过$k$。

  2. 多源汇最短路：可能有多个询问，每次询问从其中一个点走到另一点的最短距离，即起点和终点不确定（源点——起点，汇点——终点）：

    • Floyd算法（时间复杂度$O(n^3)$）

最短路问题考察的重点难点是：建图，即把原问题抽象成一个最短路问题，如何定义点和边；重点不在证明算法的正确性上。

（有向图和无向图的最短路问题其实是没有区别的，无向图可以看作是特殊的有向图，我们可以用有向图的最短路算法来解决无向图的问题。）

朴素Dijkstra

1
2
3
4
5
6
7
8
9
初始化距离 dis[1] = 0, dis[i] = 正无穷
for i 从0到n:  （集合S存当前已经确定最短距离的点）
{
    t = 找到不在S中的距离最近的点
    t加到s中
    用t更新其他点的距离（从t出去的所有边，它组成的路径能不能更新其他点的距离，即dis[x] > dis[t] + w）
}	

每次循环都可以确定一个点的最短距离，循环n次后就得到了每个点到起点的最短距离

例题：Dijkstra求最短路I（Acwing 849）

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

输入格式：第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

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

数据范围：$1 \le n \le500, 1 \le m \le 105$，图中涉及边长均不超过10000。

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<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];   //存点到起点的距离
bool st[N];    //存当前已经确定最短路的点

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;     
        for(int j = 1; j <= n; j++)    //找到不在s中的距离最近的点
            if(!st[j] && (t == -1 || dist[t] > dist[j]))  //如果dist[t]比dist[j]大的话，那t显然不满足最短路的要求
                t = j;
        
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        
        st[t] = true;   //将找到的t存入s中
    }
    
    if(dist[n] == 0x3f3f3f3f)  return -1;
    return dist[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);
    }
    
    printf("%d\n", dijkstra());
    
    return 0;
}

堆优化Dijkstra

回顾一下朴素Dijkstra算法中的各步骤的时间复杂度：

1
2
3
4
5
6
for i 从0到n:  （集合S存当前已经确定最短距离的点）
{
    t = 找到不在S中的距离最近的点————总共n^2次
    t加到s中————总共n次
    用t更新其他点的距离（从t出去的所有边，它组成的路径能不能更新其他点的距离，即dis[x] > dis[t] + w）————总共m次（与边数有关）
}

可见朴素Dijkstra算法中最耗时的是第一步：在st[]=false的点中找到dist[]最小的点，即是t，整个算法的时间复杂度为$O(n^2)$。在一组数中找到最小的数，正是堆擅长做的，在堆中求最小值的时间复杂度为$O(1)$，但这也会影响第三步，在堆中修改一个数的时间复杂度为$O(\log n)$。因此堆优化的Dijkstra算法中各步骤的时间复杂度为：

1
2
3
4
5
6
for i 从0到n:  （集合S存当前已经确定最短距离的点）
{
    t = 找到不在S中的距离最近的点————总共n次
    t加到s中————总共n次
    用t更新其他点的距离（从t出去的所有边，它组成的路径能不能更新其他点的距离，即dis[x] > dis[t] + w）————总共 m*logn次
}

可见堆优化Dijkstra算法中最耗时的变成了第三步，整个算法的时间复杂度为$O(m \log n)$。

实现堆有两种方法：手写堆（可以支持修改任意一个元素）；优先级队列（不支持修改任意一个元素，每修改一次就在队列中加一个新的数）。一般来说堆优化版的Dijkstra算法就使用STL中的优先级队列就行了。同时也要注意，稀疏图的存储方式用邻接表要好一些。

例题：Dijkstra求最短路II（Acwing 850）

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

输入格式：第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

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

数据范围：$1 \le n, m \le 1.5 \times 10^5$，图中涉及边长均不小于0，且不超过10000。

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
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1000010;

typedef pair<int, int> PII;  //first存点到起点的距离，second存点的下标（第几个点）

int n, m;
int h[N], w[N], e[N], ne[N], idx;   //稀疏图用邻接表存，与之前写过的区别是：多个w[N]来存每条边的权重（边长）
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 dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;  //小根堆
    heap.push({0, 1});
    
    while(heap.size())    //队列中最多只有m个数
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        if(st[ver])  continue;
        
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i])  //遍历从t出去的所有边，遍历完后就是遍历了所有边
        {
            int j = e[i];
            if(dist[j] > distance + w[i])    
            {
                dist[j] = distance + w[i];       //dist[j] = dist[ver] + w[i];  也是可以的
                heap.push({dist[j], j});
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f)  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);
    }
    
    printf("%d\n", dijkstra());
    
    return 0;
}

Bellman-Ford

Bellman-Ford算法是用来解决存在权重是负数的边的最短路问题的，它的主要步骤为：

1
2
3
for n 次：
    for 所有边a, b, w:  （a指向b，权重/边长为w）
        dist[b] = min(dist[b], dist[a] + w);  （和Dijkstra类型，dist[]存点到起点的最短距离）

Bellman-Ford遍历完所有边后，所有的点都满足：dist[b] <= dist[a] + w（三角不等式），这个更新的过程叫作：松弛操作。

要注意的是：若存在负权回路，则最短路不一定是存在的（若负环是在从起点到终点的某一条路径中，绕负权回路无数圈，最短路就是负无穷了）。Bellman-Ford算法可以求出是否存在负权回路，其迭代的次数是有实际意义的，如当前迭代了k次，dist[]数组的含义是从起点经过不超过K条边到各个点的最短距离；迭代完n次，第n次还有更新的话就表示存在一条最短路径，其含有的边数为n条。如果一条最短路径上有n条边，但只有n-1个点，根据抽屉原理，路径上一定存在环，且又因为第n次更新了，所有环的权重一定是负的，即存在负权回路。

例题：有边数限制的最短路（Acwing 853）

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

输入格式：第一行包含三个整数n，m，k。接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

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

数据范围：$1 \le n,k \le 500,1 \le m \le 10000$，任意边长的绝对值不超过10000。

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<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edge
{
    int a, b, w;   //a，b表示边的起点和终点，w表示边的权重
}edges[M];

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < k; i++)
    {
        //需要做个特殊的处理：每次遍历前先将dist[]数组备份一下；只用上一次迭代的结果来更新
        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);
        }
    }
    
    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++)   //读入m条边
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    
    int t = bellman_ford();
    
    if(t == -1)  puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

SPFA

SPFA算法也是用来解决存在权重是负数的边的最短路问题的，它要求路径中没有负环（负权回路），其实大多数最短路题目中都是没有负环的，SPFA算法也算是单源最短路问题中限制最少的算法了。SPFA算法相当于是在Bellman Ford算法的基础上做优化，回顾下Bellman Ford算法：

1
2
3
for n 次：
    for 所有边a, b, w:  （a指向b，权重/边长为w）
        dist[b] = min(dist[b], dist[a] + w);  （和Dijkstra类型，dist[]存点到起点的最短距离）

每次迭代要更新dist[b]时如果dist[b]在当前迭代中想要变小，那就要求dist[a]要变小，只要dist[a]变小了，dist[b]才会变小。SPFA就是从这一点作优化，利用宽度优先搜索BFS来做优化，其思路如下：

1
2
3
4
5
6
7
8
起点放入队列 queue
while queue 不空:  (queue存的是所有dist[]变小了的节点)
{
	 取出队头 t = q.fornt();
	 q.pop();
	 更新t的所有出边 t-b, 权重为w
	 	若更新成功，且队列中没有b，就把b加入队列
}

例题：SPFA求最短路（Acwing 851）

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

输入格式：第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

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

数据范围：$1 \le n,m \le 10^5$，图中涉及边长绝对值均不超过10000。

（代码与Dijkstra算法的很像）

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<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[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i])  //遍历从t出去的所有边，遍历完后就是遍历了所有边
        {
            int j = e[i];   // j表示当前这个点
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])   //当j此前不在对列中，才将j加入到队列
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f)  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(t == -1)  puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

SPFA算法也可以用来判断路径中是否存在负环（判断负环一般用SPFA算法，时间复杂度低）。

例题2：SPFA判断负环（Acwing 852）

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

输入格式：第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式：如果图中存在负权回路，则输出“Yes”，否则输出“No”。

数据范围：$1 \le n \le 2000,1 \le m \le 10000$，图中涉及边长绝对值均不超过10000。

用dist[x]数组表示从起点到当前点的最短距离，cnt[x]数组表示当前的最短路中边的数量，每次更新时有：

1
2
dist[x] = dist[x] + w[i];
cnt[x] = cnt[t] + 1;

如果过程中每一更新后cnt[x] >= 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
68
69
70
71
72
73
74
75
76
77
78
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 10010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;  
int dist[N], cnt[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++; 
}

bool spfa()
{
    //因为不需要求具体的距离了，所有不需要初始化了
    queue<int> q;
    //负环不一定是从点1开始能到达的，可能出现在以某个点为起点的路径中，所以需要把所有点加入到队列中
    for(int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }
    
    while(q.size())    
    {
        
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i])  //遍历从t出去的所有边，遍历完后就是遍历了所有边
        {
            int j = e[i];   // j表示当前这个点
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                
                if(cnt[j] >= n)  return true;
                
                if(!st[j])   //当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);
    }
    
    int t = spfa();
    if(spfa())  puts("Yes");
    else puts("No");
    
    return 0;
}

Floyd

Floyd算法是用来解决多源汇最短路问题的，时间复杂度为$O(n^3)$，其思路是：

1
2
3
4
5
6
7
用一个邻接矩阵d[i][j]存储图中所有的边;
for(k = 1; k <= n; k++)
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

循环结束之后，d[i][j]存的是从点i到点j的最短路的长度

Floyd算法是基于动态规划，$d[k, i, j]$表示从点$i$到点$j$，只经过1到$k$这些中间点，的最短距离，更新$d[k, i, j]$时有：

（关于动态规划的知识，之后会细讲。）

例题：Floyd算法求最短路（Acwing 854）

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

输入格式：第一行包含三个整数n，m，k。接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式：共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围：$1 \le n \le 200, 1 \le k \le n^2, 1 \le m \le 20000$，图中涉及边长绝对值均不超过10000。

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
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, k;
int d[N][N];  //用矩阵d存两点间的距离

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]);
}   //循环结束之后，d[i][j]就存的是点i到点j之间的最短距离了。

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    
    for(int i = 1; i <=n; i++)        //初始化距离矩阵d
        for(int j = 1; j <= n; j++)
            if(i == j)  d[i][j] = 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(k--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        
        if(d[a][b] > INF / 2)  puts("impossible");
        else printf("%d\n", d[a][b]);
    }
}