最短路径算法（ Dijkstra + Bellman-Ford + SPFA + Floyd）

一、Dijkstra 算法

Dijkstra 算法是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法，戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法。本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离，最终如果是连通的话，更新到第n个点的距离即为最短距离。需要注意的是Dijkstra 算法不能有效处理带有负权边的图。Dijkstra 算法是图论中一个较为重要的算法。其中存储所有路径的方式有两种：邻接矩阵（稠密图）、邻接表（稀疏图）。

 当图中的路径较多（路径的个数为点数的平方级别的倍数）时，我们用邻接矩阵（二维数组）来存储所有路径，我们称它为朴素版的Dijkstra 算法。时间复杂度O（n^2）。

 当图中的路径较少（路径的个数为点数为同一级别）时，我们用邻接表（多个单链表）来存储所有路径，我们称它为堆优化版的Dijkstra 算法。时间复杂度O（m*log n）。m为边数，n为点数。

 我们结合下面的例题和代码一起理解一下。

1、1 朴素版Dijkstra算法

1、1、1 Dijkstra求最短路 I题目来源：Acwing

题目难度：简单

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

输入格式:

 第一行包含整数 n 和 m。

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

输出格式:

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

数据范围:

 1 ≤ n ≤ 500,

 1 ≤ m ≤ 1e5,

 图中涉及边长均不小于 0，图中涉及边长均不超过10000。输入样例：

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

输出样例：

3

1、1、2 题解关键思路与与解答

 从上述的题目描述中，提取出重要信息：求1到n的最短距离，每个点的距离均为正。从而我们可以想到用Dijkstra算法求最短路径。我们发现图中的边数较多，所以我们在这里采用邻接矩阵来存储所有的边。我们结合下面的代码一起理解一下。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];  // 记录该点是否已经确定到第1点的距离为最短
int n,m;
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;
        }
        st[t]=true;
        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);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);  //多条路径取最短的
    }
    cout<<dijkstra()<<endl;
    return 0;
}

1、2 堆优化版Dijkstra算法

1、2、1 Dijkstra求最短路 II

题目来源：Acwing

题目难度：简单

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

输入格式：

 第一行包含整数 n 和 m。

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

输出格式：

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

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

数据范围：

 1 ≤ n,m ≤ 1.5×1e5,

 图中涉及边长均不小于 0，且不超过 10000。

数据保证：

 如果最短路存在，则最短路的长度不超过 1e9。输入样例：

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

输出样例：

3

1、2、2 题解关键思路与答案

 这道题与上面的一道题就有所差距了。该题目依然是求解1到n的最短路径，但是该题中的边数较少，那我们就可以采用堆优化版Dijkstra算法。堆优化版Dijkstra算法采用的是邻接表来存储所有路径。同时利用了小根堆，可以很快的找出当前的未确定的节点中路径最小的点，从而优化了算法的时间复杂度。我们结合代码一起理解一下：

#include<bits/stdc++.h>
using namespace std;
const int N =1.5e5+10;
typedef pair<int,int> PII;  
int h[N],e[N],ne[N],idx,w[N];
int dist[N];
bool st[N];
int n,m;
priority_queue<PII,vector<PII>,greater<PII>> q;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
int dijkstar()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.top();
        q.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]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                q.push({dist[j],j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) 
        return -1;
    return dist[n];
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dijkstar()<<endl;
    return 0;
}

二、Bellman-Ford 算法

贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼和莱斯特·福特创立的，求解单源最短路径问题的一种算法。它的原理是对图进行m次松弛操作，得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(mn)。

 Bellman-Ford算法是一种处理存在负权边的单元最短路问题的算法。解决了Dijkstra无法求的存在负权边的问题。 虽然其算法效率不高，但是也有其特别的用处。其实现方式是通过m次迭代求出从源点到终点不超过m条边构成的最短路的路径。一般情况下要求途中不存在负环。但是在边数有限制的情况下允许存在负环。因此Bellman-Ford算法是可以用来判断负环的。

 我们下面结合例题和详解来理解一下Bellman-Ford算法。

2、1 Bellman-Ford算法求有边数限制的最短路

2、1、1 题目描述

题目来源：Acwing

题目难度：简单

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

输入格式：

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

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

点的编号为 1∼n。

输出格式：

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

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

数据范围：

 1 ≤ n,k ≤ 500,

 1 ≤ m ≤ 10000,

 1 ≤ x,y ≤ n，

 任意边长的绝对值不超过 10000。输入样例：

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

输出样例：

3

2、1、2 题解关键思路与解答

注意，该体重存在负权边的路径，同时也存在负权回路。但是有边数的限制，所以我们这道题只能采用 Bellman-Ford算法。我们需要限制的k条边，我们需要迭代k次，每次算出来不超过k条边的最短路径。很重要的一点是每次迭代都是在上一次的基础上进行的，因此我们在代码实现时要注意保留上一次的结果，在上一次的基础上算。(理论中改变是同步完成的，但是实际上我们需要一个一个修改值。)我们结合代码一起理解：  

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
struct Edge
{
    int a, b, c;
}edges[M];
int n, m, k;
int dist[N];
int last[N];
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    return 0;
}

三、SPFA 算法

从上面的介绍我们知道bellmon-ford算法是带着一定的盲目性的，作为对它的优化，spfa采用类似bfs的思想，使用一个队列，只松弛那些可能更新点的距离的边。算法的流程为：

将除源点之外的所有的点当前距离初始化为无穷，并标记为未入队。源点的当前距离为0，将源点入队。

取出队首t，遍历t的所有出边，检查是否能更新所连接的点v的当前距离。如果j的当前距离被更新并且j不在队中，则将j入队。重复该操作直到队列为空。

3、1 spfa求最短路

3、1、1 题目描述

题目来源：Acwing

题目难度：简单

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

输入格式：

 第一行包含整数 n 和 m。

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

输出格式：

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

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

数据范围：

 1 ≤ n,m ≤ 1e5,

 图中涉及边长绝对值均不超过 10000

输入样例：

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

输出样例：

2

3、1、2 题解关键思路与解答

该题中存在负权边，但是不存在负回路。我们可以直接采用 spfa求最短路求取最短路。我们直接看代码。

#include<bits/stdc++.h>
using namespace std;
const int N =1.5e5+10;
int h[N],e[N],ne[N],idx,w[N];
int dist[N];
bool st[N];
int n,m;
queue<int> q;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    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;
                }
            }
        }
    }
    return dist[n];
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=spfa();
    if(t==0x3f3f3f3f)
        printf("impossible");
    else
        cout<<spfa();
    return 0;
}

四、Floyd 算法

Floyd算法又称为Floyd-Warshell算法，其实Warshell算法是离散数学中求传递闭包的算法，两者的思想是一致的。Floyd算法是求解多源最短路时通常选用的算法，经过一次算法即可求出任意两点之间的最短距离，并且可以处理有负权边的情况（但无法处理负权环）。

4、1 Floyd求最短路

4、1、1 题目描述

题目来源：Acwing

题目难度：简单

题目描述：给定一个 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。

输入样例：

1. 3 3 2
2. 1 2 1
3. 2 3 2
4. 1 3 1
5. 2 1
6. 1 3

输出样例：

1. impossible
2. 1

4、1、2 题解关键思路与解答

 Floyd本质上是动态规划的思想。倘若现在我们想求i到j的最短路径长度，我们限制这条路径上除i和j之外只准经过前k个点（这样的路径称为k允许路径），我们在算法的最外层循环每次将k加1，那么当k等于点数时求得的结果便是最优的。我们看代码：

#include<bits/stdc++.h>
using namespace std;
const int N =210,INF=1e9;
int g[N][N];
int n,m,t;
void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                g[i][j]=0;
            else
                g[i][j]=INF;
        }
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    floyd();
    while(t--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int q=g[x][y];
        if(q>INF/2)
        {
            puts("impossible");
        }
        else
        {
            printf("%d\n",q);
        }
    }
    return 0;
}

五、总结

 上述的四个求最短路径的算法都十分重要，我们应该熟悉掌握其用法，熟练写出其模板。这里给大家总结出一张图，可以根据这张图一同记忆一下