最短路算法选择

n：点数

m：边数

  • 单源最短路

    求一个点到其他所有点到最短距离。求一个点到另一个点到距离。

    • 所有边权都是正数

      • 朴素Dijkstra算法 $O(n^2)$
        • 和边数无关，适用于稠密图
        • 代码更简洁
      • 堆优化版Dijkstra算法 $O(mlog_2n)$
        • 边数少，稀疏图才用
        • 代码稍复杂
      • SPFA算法也可以用
        • SPFA的时间复杂度介于上面两者之间，有可能会被卡时间

    • 存在负权边

      • Bellman-Ford $O(nm)$

      • SPFA 相当于市Bellman-Ford的优化，一般是 $O(m)$ ，最坏是 $O(nm)$

        如果规定最多经过多少条边的话，就只能用Bellman-Ford算法

  • 多源汇最短路

    • 源点：起点

    • 汇点：终点

      起点和终点不确定的最短路问题

      Floyd算法 $O(n^3)$

Dijkstra算法

朴素版

算法流程

S：当前已经确定最短距离的点。

  1. 初始化距离

    dist[1]=0, dist[i] = +INF

    即，只有起点的距离是确定的，遍历到了的

  2. 遍历找到不在S中的距离最近的点

    1
    2
    3
    4
    for i: 1 ~ n:
    	t = 不在 S 中的距离最近的点
        s = t
        用 t 更新其他点的距离

    这样遍历之后就可以确定每一个点的距离

例题

给定一个 n 个点 m 个边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点到最短距离，如果无法从 1 号点走到 n 好点，则输出 -1.

输入格式

第一行包含整数 n 和 m

接下来 m 行，每行包含三个整数 x ， y， z，表示点 x 和 y 之间存在一条有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点到最短距离

如果路径不存在，则输出 -1.

数据范围

输入样例

1
2
3
4
3 3
1 2 2
2 3 1
1 3 4

输出样例

1
3

解答

流程图讲解

为了直观理解，画图：

image-20240304175313190

「第一步」：初始化距离：

image-20240304175438387

这个时候把 1 号点加入集合 S 中，表示已经确定的点。

「第二步」，迭代距离：

  1. 现在迭代的是 1 号点到其他点到距离。用 1 号点更新其他点的距离。

    • 2 号点： 原来的值（正无穷） > 距离（2）。更新距离为 2

    • 3 号点： 原来的值（正无穷） > 距离（4）。更新距离为 4

      备注：如果无法到达就还是无穷，不更新

      image-20240304175548156

  2. 现在1号点是确定的点，之后遍历，不确定的点中到确定点距离最近的点。也就是这里距离为 2 的 2 号点。

    • 1 号点是已经确定的点了，距离不用更新

    • 3 号点

      更新后的距离：2号点的距离+2号点到3号点点权重 = 2 + 1 = 3

      原来的值（4） > 更新后的距离（3）。更新距离为 3.

      image-20240304175705426

  3. 继续迭代剩下的未确定点中距离最小的点。这里是 3 号点。

    1 号点和 2 号点都已经确定了，所以没有更新。

最终，迭代了 3 次（3个点），结果是每个点到起点 1 号点点距离都确定了。

因为要遍历查找 n 个点，每次找n个点更新距离和找下一个不在S中的点都是n次，最终就是$O(n^2)$

因为朴素Dijkstra更适用于稠密图，稠密图使用邻接矩阵点方式存储。

注意，题目中说到有重边和自环。

  • 重边：A 点到 B 点有两条路可以走
  • 自环：自己可以到自己这个点

在最短路问题中，重边只保留距离最短的就行了，自环不要。

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

using namespace std;

const int N = 500;

int n, m;    // n 个点， m 条边
int g[N][N]; // 邻接矩阵
int dist[N]; // 每个点到起点的距离
bool st[N];  // 已确定的点的集合

int dijkstra() {
    // 初始化距离
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    // 迭代 n 次
    for (int i = 0; i < n; ++i) {
        // 先找没有确定距离的点中，距离最短的点（找点）
        int t = -1; // 此次遍历确定的点
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;

        st[t] = true; // 加入到已确定的点

        // 用 t 更新其他点点距离
        for (int j = 1; j <= n; ++j) 
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

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

int main() {
    // 输入
    cin >> n >> m;

    // 初始化
    memset(g, 0x3f, sizeof(g));

    // 读入 m 条边
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); // 注意这里这道题会出现重边，只需要选择最小的
    }

    int t =  dijkstra();

    cout << t << endl;

    return 0;
}

堆优化版

分析朴素Dijkstra的运行过程，发现导致算法速度慢的主要问题是在找点上（找不在集合中的，距离最近的点）

刚好可以利用堆进行优化，使得找最近点点点复杂度为$O(1)$

堆一般是两种写法：

  • 手写。可以自己控制细节。手写复杂。
  • 优先队列。不支持修改任意元素。

堆优化算法一般用于稀疏图，稀疏图一般使用邻接表存储。

题目如上，相同。

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII; // 堆中存储的实际是pair

const int N = 100010;

int n, m;                          // n 个点， m 条边
int h[N], e[N], w[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 dijkstra() {
    // 初始化各点距离
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap; //  小根堆
    heap.push({0, 1});

    while (heap.size()) {
        auto t = heap.top(); // 类似于 {0,  1} 0表示距离，1表示点的编号
        heap.pop();

        int ver = t.se, distance = t.fi;
        if (st[ver]) continue; // 如果该点已经确定就继续
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main() {
    // 输入
    cin >> n >> m;

    // 初始化
    memset(h, -1, sizeof(h));

    // 读入 m 条边
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int t =  dijkstra();

    cout << t << endl;

    return 0;
}

Bellman-Ford

对于有负权边的图，一定要知道，当经过负权回路时是没有最短路径的（负无穷）。

Bellman-Ford算法可以求出是否有负权回路。但是使用SPFA算法的要求是不存在负环。

最多经过k条边是Bellman-Ford的特点，这种问题只能用Bellman-Ford算法来做。

基本思路

1
2
3
4
5
6
初始化

for n次
    备份
    for 所有边 a，b, w （从a到b，边权为w）
       	dist[b] = min(dist[b], dist[a] + w)

例题

题目（注意根据题目分析算法的受用情况）

给定一个n个点，m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号走到 n 点，输出 impossible

输入格式

第一行包含三个整数n，m，k。

接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式

输出一个整数，表示从 1 号到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

输入样例

1
2
3
4
3 3 1
1 2 1
2 3 1
1 3 3

输出样例

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

using namespace std;

const int N = 510, M = 10010;

int n, m, k;            // n 个点，m 条边，最多经过k条边
int dist[N], backup[N]; // dist表示到每个点最近的距离,backup是备份数组

struct Edge {
    int a, b, w;
}edges[M];

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

    memcpy(backup, dist, sizeof(dist)); // 备份
    for (int i = 0; i < k; ++i) { // 最多找到 k 个边
        for (int j = 0; j < m; ++j) { // 遍历 m 条边
            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() {
    cin >> n >> m >> k;

    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int t = bellman_ford();

    if (t == -1) puts("impossible");
    else cout << t << endl;

    return 0;
}

SPFA

实际上是Bellman-Ford算法的优化，唯一缺点是在存在负权环的情况下不能用。但是很少有存在负权环的图。

1
2
3
4
5
6
初始化一个队列 （queue <- 1号点）
while 队列不为空
	取出队首元素 t
    更新 t 的所有出边 t -> b (权重为w)
    	如果 b 变小了
    		queue <- b

队列里存的是变小的点（如果没有变小那么后继的点就不会变）。点变小之后，后继的点可能就会变小，所以需要对它的出边遍历。

例题

题目（基础）

给定一个n个点，m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从 1 号点到 n 号点的最短距离，如果无法从 1 号走到 n 点，输出 impossible

输入格式

第一行包含三个整数n，m。

接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式

输出一个整数，表示从 1 号到 n 号点的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

输入样例

1
2
3
4
3 3
1 2 5
2 3 -3
1 3 4

输出样例

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 510;

int n, m;   // n个点，m条边
int dist[N];    // 最短距离
int h[N], e[N], w[N], ne[N], idx; // 邻接表存图
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]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

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

int main() {
    cin >> n >> m;

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

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int t = SPFA();

    if (t == -1) puts("impossible");
    else cout << t << endl;
    
    return 0;
}

题目2（判断负环）

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你判断图中是否存在负权回路。

注意不是判断从1开始的负环

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z表示点x和点y之间存在一条有向边，边长为z。

输出格式

如果图中存在负权回路则输出“Yes”

否则输出“No”

数据范围

输入样例

1
2
3
4
3 3
1 2 -1
2 3 4
3 1 -4

输出样例

1
Yes

代码

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

using namespace std;

const int N = 510;

int n, m;   // n个点，m条边
int dist[N], cnt[N];    // dist表示最短距离，cnt表示到该点经过点边数
int h[N], e[N], w[N], ne[N], idx; // 邻接表存图
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]) {
            int j = e[i];
            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]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false; // 不存在负环
}

int main() {
    cin >> n >> m;

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

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if(SPFA()) puts("Yes");
    else puts("No");

        
    return 0;
}

Floyd

Floyd是适用于多源汇最短路问题，所以它的存储方式也和一般情况不同，用d[i,j]表示从 i 到 j 的最短路径。

在算法中这个d[i][j]其实也就是邻接矩阵存图的i到j的边。

大概思路

1
2
3
4
5
初始化 d[i][j]
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])

原理其实是基于动态规划。

例题

题目

给定一个 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
2
3
4
5
6
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

样例输出

1
2
impossible
1

代码

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

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;    // 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() {
    cin >> n >> m >> Q;

    // 初始化邻接矩阵
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j)
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w); // 如果有重边，则保留权重最小的
    }

    floyd();

    for (int i = 0; i < Q; ++i) {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > INF / 2) puts("impossible");
        else cout << d[a][b] << endl;
    }

    return 0;
}