问题重现#

问题来自洛谷-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$ 之间的边进行松弛．

使用代码表示如下：

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

cpp

Floyd 算法#

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

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

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

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

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

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

    for (int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                // 尝试使用点k对从点i到点j之间的边进行松弛
}
int main(){
    int s;
    cin >> n >> m >> s;

    // 输入数据
    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    floyd();

    for (int i = 1; i <= n; i++) {
        if (dist[s][i] == INF) {
            cout << "2147483647 "; // 输出2^31-1
        } else {
            cout << dist[s][i] << " ";
        }
    }
    cout << endl;
}

cpp

但是，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 算法对于处理带有负权的图是最快的．

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

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

cpp

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

dijkstra 算法#

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

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

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

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

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

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

cpp

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

dijkstra 算法优化#

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

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

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

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

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

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

void dijkstra(int s){
    // 初始化
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));

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

cpp

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

最短路算法比较#

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

标程#

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

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

int n, m;

int cnt;
int fi[N];
int ne[M];
int to[M];
int co[M];

void add(int u, int v, int w){
    cnt++;
    ne[cnt] = fi[u];
    fi[u] = cnt;
    to[cnt] = v; co[cnt] = w;
}

int dist[N];
bool vis[N];

struct Node {
    int dist;
    int id;
    friend bool operator<(Node a, Node b){
        return a.dist > b.dist;
    }
};

void dijkstra(int s){
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));

    priority_queue<Node> q;
    dist[s] = 0;
    q.push({0, s});
    while(!q.empty()){
        Node tmp = q.top();
        q.pop();
        int x = tmp.id;
        if (vis[x]) continue;
        vis[x] = true;
        for (int i = fi[x]; i != 0; i = ne[i]){
            int v = to[i], w = co[i];
            if (dist[v] > dist[x] + w){
                dist[v] = dist[x] + w;
                q.push({dist[v], v});
            }
        }
    }
}

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

    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }

    dijkstra(s);

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << 2147483647 << " ";
        } else {
            cout << dist[i] << " ";
        }
    }
    cout << endl;
    return 0;
}

cpp