问题重现#

问题来自洛谷-P4779，选取问题时稍作了更改．

题目：P4779【模板】单源最短路径

题目描述#

给出一个有向图，请输出从某一点出发到所有点的最短路径长度．

输入格式#

第一行包含三个整数 $n,m,s$ ，分别表示点的个数、有向边的个数、出发点的编号．

接下来 $m$ 行每行包含三个整数 $u,v,w$ ，表示一条 $u \to v$ 的，长度为 $w$ 的边．

输出格式#

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$ ．

数据范围#

对于 $100\%$ 的数据： $1 \leq n \leq 10^5$ ； $1 \leq m \leq 2\times 10^5$ ； $1 \leq u_i, v_i\leq n$ ； $0 \leq w_i \leq 10 ^ 9$ ； $0 \leq \sum w_i \leq 10 ^ 9$ ．

最短路算法#

注：为了表示方便，我们将从 $a$ 到点 $b$ 之间的边的权重表示为 g[a][b]，如果没有边则为 INF．

在介绍最短路之前，我们需要了解一个概念：松弛

我们已知有两个点 $a$ 、 $b$ ，它们之间的最短距离为 g[a][b]．我们尝试使用第三个点 $c$ ，如果从 $a$ 点经过 $c$ 点再到 $b$ 点比从 $a$ 点直接到 $b$ 点所需要的路程少，则将最短距离更新．这样的操作叫做使用 $c$ 对从点 $a$ 到点 $b$ 之间的边进行松弛．

使用代码表示如下：

1
g[a][b] = max(g[a][b], g[a][c] + g[c][b]);

Floyd 算法#

Floyd 算法很简单，它的本质是动态规划．

我们首先定义一个二维数组 dist[i][j]，表示从点 $i$ 到点 $j$ 的最短距离．输入数据时，类似邻接矩阵，直接将数据输入 dist 数组．

而后，枚举每一个 $k$ , $i$ , $j$ ，尝试使用点 $k$ 对从点 $i$ 到点 $j$ 之间的边进行松弛．

枚举完成后，此时的 dist 数组就是最终的结果．

Floyd 算法不仅可以解决单源最短路的题目，还可以解决多源单目标最短路的问题．

1
#include <bits/stdc++.h>
2
#define N (int)1e5 // 最多可能有的节点数
3
#define M (int)2e5 // 最多可能有的边数
4
#define INF 0xffffff // 极大值，代表无穷
5
using namespace std;
6
int n, m, dist[N][N];
7
void floyd()
8
{
9
  // 初始化数据
10
    for (int i = 1; i <= n; i++){
11
        for (int j = 1; j <= n; j++){
12
            if (i == j) dist[i][j] = 0; // 自己到自己的距离为0
13
            else dist[i][j] = INF;
14
        }
15
    }
16

17
    for (int k = 1; k <= n; k++) // k 一定要在最外层
18
        for(int i = 1; i <= n; i++)
19
            for(int j = 1; j <= n; j++)
20
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
21
                // 尝试使用点k对从点i到点j之间的边进行松弛
22
}
23
int main(){
24
    int s;
25
    cin >> n >> m >> s;
26

27
    // 输入数据
28
    for (int i = 1; i <= m; i++){
29
        int u, v, w;
30
        cin >> u >> v >> w;
31
        dist[u][v] = w;
32
    }
33

34
    floyd();
35

36
    for (int i = 1; i <= n; i++) {
37
        if (dist[s][i] == INF) {
38
            cout << "2147483647 "; // 输出2^31-1
39
        } else {
40
            cout << dist[s][i] << " ";
41
        }
42
    }
43
    cout << endl;
44
}

但是，Floyd 算法太慢了，时间复杂度到达了 $O(n^3)$ ，因为基于邻接矩阵，空间复杂度也达到了 $O(n^2)$ ，所以只能拿到部分分．

SPFA 算法#

我们可以定义一个数组 dist[i]，表示从源点 $s$ 到 $i$ 的最小距离．初始时每一项都是无穷大，而后将 dist[s] 设定为 0，表示从源点 $s$ 到本身的最小距离为 0．之后，对于每个目标点 $i$ （一开始是 $s$ ）的每一个相邻节点 $j$ ，都尝试使用点 $i$ 对从点 $s$ 到点 $j$ 的边进行松弛．而后，将 $j$ 选中为目标点，重复．直到没有待被选中的点位置，此时的 dist 数组就是最终的结果，类似于广度优先搜索．

SPFA 算法对于处理带有负权的图是最快的．

以下是基于链式前向星的源代码：

1
int dist[N]; // dist[i]表示从源点到i的最小距离
2
bool vis[N]; // 检查是否在队列中
3
void spfa(int s){
4
// 在dist数组中记录从s出发到每个点的最短路
5
    for(int i = 1;i <= n;i++){ // 初始化
6
        dist[i] = INF; // 从s到每一个点都暂时无法到达
7
        vis[i] = false; // 每一个节点都没有被访问过
8
    }
9
    queue<int> q; // 类似于bfs中的队列，储存待被松弛的目标点
10
    q.push(s); // 将s设定为目标点
11
    vis[s] = true; // s现在在队列中
12
    dist[s] = 0; // 从源点s到本身的最小距离为0
13
    while(!q.empty()){ // 直到q为空时才停止
14
        int x = q.front(); // 将x设为当前的目标点
15
        q.pop(); // 从待办清单中移除
16
        vis[x] = false; // 移除标记
17
        for(int i = fi[x]; i != 0; i = ne[i]){
18
        // 使用链式前向星寻找所有x的相邻节点
19
                int v = to[i], w = co[i];
20
                if (dist[v] > dist[x] + w){
21
                    dist[v] = dist[x] + w; // 松弛
22
                    if (!vis[v]) { // 只有当v不在队列中时才将其加入队列
23
                            q.push(v); // 将v入队
24
                            vis[v] = true; // 将v标记为在队列中
25
                    }
26
                }
27
        }
28
    }
29
}

显然，SPFA 算法的时间复杂度在最坏的情况下为 $O(nm)$ ，仍旧无法拿到满分．

dijkstra 算法#

我们仍旧可以像 SPFA 一样，定义一个 dist 数组，不过，在松弛的时候，我们需要选取 dist 数组中最小的一个节点 $i$ ，对于 $i$ 的每一个相邻节点 $j$ ，都尝试使用 $i$ 来对从节点 $s$ 到节点 $j$ 的这条边进行松弛，直到每一个点都被选中作为点 $i$ 过，此时的 dist 数组就是最终的结果．

dijkstra 其实就是 SPFA 的贪心版本．

以下是基于链式前向星的源代码：

1
int dist[N];
2
bool vis[N]; // 检查是否在已经被选中过
3
void dijkstra(int s){
4
// 以s为原点进行松弛
5
    for(int i = 1;i <= n;i++){ // 初始化
6
        dist[i] = INF; // 从s到每一个点都暂时无法到达
7
        vis[i] = false; // 每一个节点都没有被访问过
8
    }
9
    dist[s] = 0; // s到自己的距离为0
10
    for (int i = 1; i <= n; i++) // 依次选择每一个节点
11
    {
12
      // 找出dist中最小且没有被选择过的一项
13
        int minn = -1; // minn表示最小的一项的索引
14
        for(int j = 1; j <= n; j++){
15
            if (vis[j]) continue; // 如果被选择过，则不会再次被选择
16
            if (minn == -1 || dist[j] < dist[minn]) minn = j;
17
        }
18

19
        if (dist[minn] == INF) continue;
20
        // 如果被选择的这个节点无法到达，则这个节点不能被选中
21

22
    // 使用链式前向星进行遍历
23
        for(int j = fi[minn]; j != 0; j = ne[j])
24
        {
25
          // 松弛
26
            dist[to[j]] = min(dist[to[j]], dist[minn] + co[j]);
27
        }
28
        vis[minn] = true; // 将minn这个节点标记为已被选择过
29
    }
30
}

显然，dijkstra 算法的时间复杂度在最坏的情况下为 $O(n^2)$ ，仍旧无法拿到满分．此外，此算法无法处理含有负权边的图．

dijkstra 算法优化#

dijkstra 算法可以利用堆进行优化．

宏观整个算法，最浪费时间的事情就是找出 dist 中最小的一项，因此我们就想到了使用堆来优化．

在赛场上直接实现堆不太现实，因此我们可以使用 C++STL 优先队列来快速查找最小的一项．

以下是基于链式前向星的源代码：

1
int dist[N];
2
bool vis[N]; // 检查是否在队列中
3

4
struct Node {
5
    int dist; // 距离
6
    int id; // 节点编号
7
    friend bool operator<(Node a, Node b){
8
        return a.dist > b.dist; // 此时如果返回true，则表示a的优先级低于b
9
    }  // 由于优先队列是大的元素优先，所以需要重载运算符，使得dist小的元素优先
10
};
11

12
void dijkstra(int s){
13
    // 初始化
14
    memset(dist, 0x3f, sizeof(dist));
15
    memset(vis, 0, sizeof(vis));
16

17
    priority_queue<Node> q; // 优先队列，用于存储节点
18
    dist[s] = 0; // s点到s点的距离为0
19
    q.push({0, s}); // 将s点加入队列
20
    while(!q.empty()){ // 当队列为空时，立即结束
21
        Node tmp = q.top(); // tmp为队列中最小的元素，获得最小的元素
22
        q.pop(); // 将最小的元素弹出
23
        int x = tmp.id; // x为获得的最小的元素的节点编号
24
        if (vis[x]) continue; // 如果曾经被访问过，就跳过不访问
25
        vis[x] = true; // 标记为访问过
26
        for (int i = fi[x]; i != 0; i = ne[i]){ // 遍历所有以x为起点的边
27
            int v = to[i], w = co[i]; // v为终点，w为权值
28
            if (dist[v] > dist[x] + w){ // 松弛操作：如果从s到v的距离大于从s到x的距离加上x到v的距离
29
                dist[v] = dist[x] + w; // 就更新从s到v的距离
30
                q.push({dist[v], v}); // 将v点加入队列
31
            }
32
        }
33
    }
34
}

这样的算法可以达到时间复杂度是 $O(n\log n)$ ，可以完成这道题目．

最短路算法比较#

算法	时间复杂度	是否可以有负权边	使用场景
Floyd	$O(n^3)$	是	多源最短路
SPFA	最差 $O(nm)$	是	在有负权时
dijkstra	$O(n^2)$	否	建议使用其优化版
dijkstra 优化	$O(n\log n)$	否	没有负权时

标程#

以下的代码在洛谷中提交后，100% 的样例是 AC 的．

1
#include <bits/stdc++.h>
2
#define N (int)1e5 + 100
3
#define M (int)2e5 + 100
4
#define INF 0xffffff
5
using namespace std;
6

7
int n, m;
8

9
int cnt;
10
int fi[N];
11
int ne[M];
12
int to[M];
13
int co[M];
14

15
void add(int u, int v, int w){
16
    cnt++;
17
    ne[cnt] = fi[u];
18
    fi[u] = cnt;
19
    to[cnt] = v; co[cnt] = w;
20
}
21

22
int dist[N];
23
bool vis[N];
24

25
struct Node {
26
    int dist;
27
    int id;
28
    friend bool operator<(Node a, Node b){
29
        return a.dist > b.dist;
30
    }
31
};
32

33
void dijkstra(int s){
34
    memset(dist, 0x3f, sizeof(dist));
35
    memset(vis, 0, sizeof(vis));
36

37
    priority_queue<Node> q;
38
    dist[s] = 0;
39
    q.push({0, s});
40
    while(!q.empty()){
41
        Node tmp = q.top();
42
        q.pop();
43
        int x = tmp.id;
44
        if (vis[x]) continue;
45
        vis[x] = true;
46
        for (int i = fi[x]; i != 0; i = ne[i]){
47
            int v = to[i], w = co[i];
48
            if (dist[v] > dist[x] + w){
49
                dist[v] = dist[x] + w;
50
                q.push({dist[v], v});
51
            }
52
        }
53
    }
54
}
55

56
int main(){
57
    int s;
58
    cin >> n >> m >> s;
59

60
    for (int i = 1; i <= m; i++){
61
        int u, v, w;
62
        cin >> u >> v >> w;
63
        add(u, v, w);
64
    }
65

66
    dijkstra(s);
67

68
    for (int i = 1; i <= n; i++) {
69
        if (dist[i] == INF) {
70
            cout << 2147483647 << " ";
71
        } else {
72
            cout << dist[i] << " ";
73
        }
74
    }
75
    cout << endl;
76
    return 0;
77
}

音乐

音乐

问题重现#

题目描述#

输入格式#

输出格式#

数据范围#

最短路算法#

Floyd 算法#

SPFA 算法#

dijkstra 算法#

dijkstra 算法优化#

最短路算法比较#

标程#

文章分享