常见的五种最短路算法

摘要

本文主要介绍关于图的最短路的五种常用算法和其应用。朴素Dijkstra， 堆优化Dijkstra，Bellman-Ford，SPFA， Floyd。这几种算法有各自的优势和劣势，适用于不同的场景。文章的难度不大，适合算法初学者学习。

五种最短路算法之间的区别

在这里插入图片描述
注：n表示图中点的数目，m表示图中边的数目。

朴素Dijkstra

算法介绍

  • DijKstra的核心思想是贪心。
  • 先将起点距离自己的距离设为0，其余设为正无穷。
  • 一共循环n次，每一次循环，找到目前没有被找到过并且距离起点最近的点。此时，被找到的这个点所记录的距离，正是这个点到起点的最短距离。然后再用这个点来更新与它有连接的其它点的距离。
  • 每一次循环，我们都能找到一个满足条件的点，n次循环过后，我们就可以得到每一个点距离起点的最短距离了。
  • 时间复杂度为o(n^2)，n 表示点数，m表示边数，可以用邻接矩阵存图。
  • 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
int g[N][N];  // 用邻接矩阵存图，存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
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 ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

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

        st[t] = true;
    }

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

例题：AcWing 849. Dijkstra求最短路 I

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

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

输入格式
第一行包含整数 n 和 m。

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

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

如果路径不存在，则输出 −1。

数据范围
1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

int mp[510][510],dis[510],n,m;
bool st[510];

int Dijkstra(){
    memset(dis,0x3f,sizeof dis);

    dis[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dis[t]>dis[j]))     
                t=j;
        }

        st[t]=true;
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],dis[t]+mp[t][j]);
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    return dis[n];
}
int main(){
    cin>>n>>m;
    memset(mp,0x3f,sizeof mp);
    int x,y,z;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&z);
        if(x!=y){
            mp[x][y]=min(mp[x][y],z);
        }
    }
     cout<<Dijkstra()<<endl;
    return 0;
}

堆优化Dijkstra

思想

  • 在朴素版的Dijkstra中，我们每次找距离起点最近的点所花费的时间都是o(n)的，容易想到用堆来优化这一查找。
  • c++的stl中priority_queue就是用堆实现的，我们可以直接使用。
  • 时间复杂度为o(mlogn)，n 表示点数，m表示边数，应该用邻接表存图。

核心代码

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
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        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])
        {
            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;
    return dist[n];
}

例题：AcWing 849. Dijkstra求最短路 II

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

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

输入格式
第一行包含整数 n 和 m。

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

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

如果路径不存在，则输出 −1。

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

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
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
49
50
51
52
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
int n,m,dis[200000];
vector<PII> mp[200000];
bool st[200000];

int Dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII>> Q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    Q.push({0,1});

    while(!Q.empty()){
        auto t=Q.top();
        Q.pop();
        int disten=t.first,no=t.second;
        if (st[no]) continue;
        st[no] = true;

        if(!mp[no].empty()){
            for(int i=0;i<mp[no].size();i++){
                PII j=mp[no][i];
                if(!st[j.second]&&dis[j.second]>disten+j.first){
                    dis[j.second]=disten+j.first;
                    Q.push({dis[j.second],j.second});
                }
            }
        }
    }
    if (dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}

int main()
{   
    cin>>n>>m;
    int x,y,z;
     for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&z);
        if(x!=y){
            mp[x].push_back({z,y});
        }
    }
    cout<<Dijkstra()<<endl;
    return 0;
}

Bellman-Ford

算法介绍

  • Bellman-ford 算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。缺点是时间复杂度过高，高达O(nm), n为顶点数，m为边数。
  • 首先介绍松弛函数：对边集合 m中任意边，以 g[u][v] 表示顶点 u 出发到顶点 v 的边的权值，以 dis[v] 表示当前从起点 s 到顶点 v 的路径权值。
    若存在边 g[u][v]，使得：
    dis[v] > dis[u] + g[u][v] 则更新 dis[v] 值：dis[v] = dis[u] + g[u][v]
    所以，松弛函数的作用，就是判断是否经过某个顶点，或者说经过某条边，可以缩短起点到终点的路径权值。
  • 先将起点距离自己的距离设为0，其余设为正无穷。
  • n次循环，在每次循环中，遍历所有边，对每一条边，判断是否可以进行松弛操作。第k次循环过后，我们可以得到：从起点经过不超过k条边所能到达的点的最短距离。
  • 时间复杂度为o(nm)，n 表示点数，m表示边数，可以直接用结构图存储每一条边。

核心代码

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
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

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

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[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≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
using namespace std;

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

int n,m,k,dis[510],back[510];

bool Bellman_Ford(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
        for (int i = 1; i <= k; i ++ ){
            memcpy(back, dis, sizeof dis);
            for (int j = 1; j <= m; j ++ ){
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dis[b] = min(dis[b], back[a] + w);
        }
    }

    if (dis[n] > 0x3f3f3f3f / 2) return false;
    return true;
}
int main() {

    cin>>n>>m>>k;
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        edges[i].a=x;
        edges[i].b=y;
        edges[i].w=z;
    }
    if(Bellman_Ford()){
        cout<<dis[n];
    }else{
        cout<<"impossible";
    }
    return 0;
}

SPFA

算法介绍

  • 基于Bellman-Ford之外，可以确定，松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。
  • 将前导节点松弛成功过的节点放在队列中，每次取出一个元素进行松弛操作，直到队中没有元素。
  • 值得一提的是，如果图中存在负环，可以用一个数组 cnt[x] 存储1到x的最短路中经过的点数，当cnt[x]>n，就说明有负环。
  • 时间复杂度一般情况为o(m)，最坏情况为O(mn)，（在最坏情况的时间复杂度与Bellman-Ford算法相同）。

核心代码

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

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

    while (q.size())
    {
        auto 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])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

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

例题1：AcWing 851. spfa求最短路

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

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

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

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

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

如果路径不存在，则输出 impossible。

数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
vector<PII> mp[100010];
int dis[100010],n,m;
bool st[100010];

bool spfa(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    queue<int> Q;
    Q.push(1);
    st[1] = true;
    while(!Q.empty()){
        int t=Q.front();
        Q.pop();
        st[t]=false;
        if(!mp[t].empty()){
            for(int i=0;i<mp[t].size();i++){
                PII e=mp[t][i];
                if(dis[e.second]>dis[t]+e.first){
                    dis[e.second]=dis[t]+e.first;
                    if(!st[e.second]){
                        Q.push(e.second);
                        st[e.second]=true;
                    }
                }
            }
        }
    }
    if(dis[n]>0x3f3f3f3f/2){
        return false;
    }
    return true;
}
int main() {
    cin>>n>>m;
    int x,y,z;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&z);
        mp[x].push_back({z,y});
    }
    if(spfa()){
        cout<<dis[n];
    }else{
        cout<<"impossible";
    }
    return 0;
}

例题2：ACWing 852. spfa判断负环

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

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

输入格式
第一行包含整数 n 和 m。

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

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

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

输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
vector<PII> mp[2020];
int n,m,dis[2020],cnt[2020];
bool st[2020];
bool spfa(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=false;
        if(!mp[t].empty()){
            for(int i=0;i<mp[t].size();i++){
                PII e=mp[t][i];
                if(dis[e.second]>dis[t]+e.first){
                    cnt[e.second]=cnt[t]+1;
                    if(cnt[e.second]>=n) return false;
                    dis[e.second]=dis[t]+e.first;
                    if(!st[e.second]){
                        st[e.second]=true;
                        q.push(e.second);
                    }
                }
            }
        }
    }
    return true;
}
int main() {
    cin>>n>>m;
    int x,y,z;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&z);
        mp[x].push_back({z,y});
    }
    if(!spfa()){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}

Floyd

算法介绍

  • Floyd是一种求多源最短路的方法，核心思想是动态规划。
  • f[i, j, k]表示从 i 走到 j 的路径上除 i 和 j 点外只经过 1 到 k 的点的所有路径的最短距离。
  • 那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
    因为在计算第k层的f[i, j]的时候要先将第k - 1层的所有状态计算出来，所以我们只用开一个二维数组 f[i][j] 。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始化：
    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;

// 算法结束后，d[a][b]表示a到b的最短距离
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]);
}

例题：AcWing 854. Floyd求最短路

给定一个 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≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
#include<queue>
using namespace std;
int n,m,k;

int mp[210][210];
void Floyd(){

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
               mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
    }
}
int main() {
    cin>>n>>m>>k;
    int x,y,z;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j!=i) mp[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        mp[x][y]=min(mp[x][y],z);
    }
    Floyd();
    for(int i=1;i<=k;i++){
        scanf("%d%d",&x,&y);
        if(mp[x][y]>0x3f3f3f3f/2){
            printf("impossible\n");
        }else{
             printf("%d\n",mp[x][y]);
        }
    }
    return 0;
}