您现在的位置是：首页 > 其他

当前栏目

【算法】最短路算法

算法

2023-04-18 16:30:09 时间

😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

在这里插入图片描述

文章目录

📗前言
📘最短路算法
📙后记

📗前言

咕咕咕，我是🕊白晨，最近一直在忙开学考试，托更了很久，果咩纳塞😱。

这次为大家分享的是图论中的最短路算法。考虑到最短路算法的复杂性以及本文新手向的教程，本次算法讲解列举了大量例子并且配上了大量动图。本篇文章所有的代码实现都是算法向的，以快速实现和效率为主，如果出现算法向的代码实在看不懂，可以参考白晨的工程向实现的代码，工程向代码链接：Graph。

📘最短路算法

最短路算法是指一个图中，求某一个节点到其他节点的最短路径（最小权值路径）的算法。

最短路算法是图论中一类很重要的算法，也是算法题中经常会使用的一类算法。这种算法也可以和实际问题结合起来，比如你要从西安到上海，要找到用时最短的一条路径，就需要这种算法。

🎗️Dijkstra

🍕朴素Dijkstra算法

🍬原题链接：Dijkstra求最短路 I

🪅算法思想：

朴素Dijkstra算法为单源最短路算法，适合稠密图，时间复杂度为 $O(n^2)$ （n为节点个数），对于边的存储结构为 邻接矩阵。

注意：Dijkstra算法必须要保证所有边的权值为正，否则算法的贪心策略证明失效。

具体做法

初始化 dist 数组（初始化为无限大）以及 $d i s t [1] = 0$ （一号节点到自己的距离为0）。
遍历 dist 数组，选出其中距离最短的节点，选中此节点加入已确定最短距离的节点的集合S。
根据上面确定节点的最短距离更新到达其他节点的最短距离（S集合中节点距离不可能再被更新）。
重复2、3过程 N 次，N次迭代后，全部点的最短距离已经被确定。

以上的思想本质上来说是一种贪心策略，为什么能保证每次选中的距离1号节点最近的节点的路径就是最短路径呢？

Dijsktra迪杰斯特拉算法的证明（数学归纳法）和代码实现

证明见上面文章。

现在，我们来模拟一下Dijkstra算法的具体流程：

动画演示如下：

Dijkstra

🪆代码实现：

// 朴素Dijkstra算法
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;

int g[N][N]; // 邻接矩阵
int dist[N]; // 存储最短距离
bool book[N]; // 是否已确定最短路

int Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    // 循环n次
    for (int i = 0; i < n; ++i)
    {
        // 选出距离1号节点距离最短的节点
        int u = -1;
        for (int j = 1; j <= n; ++j)
            if (!book[j] && (u == -1 || dist[u] > dist[j])) u = j;
        book[u] = true;

        // 更新边
        for (int i = 1; i <= n; ++i)
            if (!book[i] && dist[u] + g[u][i] < dist[i]) dist[i] = dist[u] + g[u][i];
    }

    if (dist[n] == INF) return -1;
    else return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));

    while (m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = min(g[a][b], w); // 重边保留最小的边
    }

    printf("%d", Dijkstra());
    return 0;
}

🍔堆优化Dijkstra算法

🍬原题链接：Dijkstra求最短路 II

🪅算法思想：

堆优化Dijkstra算法为单源最短路算法，适用于稀疏图，时间复杂度为 $O (m l o g n)$ （m为边数，n为节点数），边的存储结构为邻接表。

相比于朴素版，本算法对于寻找路径最短的节点的过程进行了优化，改为了用小根堆堆存储最短路径，根据小根堆的特性，最短的路径就是堆顶元素，这样就省去了寻找最短路径的过程。

注意：Dijkstra算法必须要保证所有边的权值为正，否则算法的贪心策略证明失效。

具体做法
1. 初始化 dist 数组， $d i s t [1] = 0$ ，将{0,1}（距离为0，节点序号为1）入堆。
2. 出堆顶元素，根据新确定最短路径以及节点下标更新其他路径（本次选用的存储结构为邻接表，所以直接遍历每个节点对应的链表即可）。
3. 重复2过程，直到堆为空。

🪆代码实现：

// 堆优化Dijkstra算法
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010, INF = 0x3f3f3f3f;

int n, m;

// 这里只是我习惯的邻接表存储方式，也可以用结构体存储，只要能遍历一个节点的所有出边就可以
int g[N], e[N], ne[N], val[N], idx;// g为邻接表，e，ne，val为单链表，e存放节点序号，ne存放子节点下标，val存储权值
bool book[N]; // 此节点是否已经确定最短路径
int dist[N]; // 存储到1号节点的最短路径大小

// 加边
void add(int a, int b, int w)
{
    e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq; // 小根堆
    pq.push({0, 1}); // 前面为距离，后面为节点序号
    
    while (pq.size())
    {
        auto t = pq.top();
        pq.pop();
        int st = t.first, node = t.second;
        // 由于题目有重边，所以可能会把一个节点更新多次，由于小根堆是距离小的先出，所以小边会先出确定最短路径，后面出的直接忽略即可
        if (book[node]) continue; 
        book[node] = true;
        
        for (int i = g[node]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[node] + val[i] < dist[j])
            {
                dist[j] = dist[node] + val[i];
                pq.push({dist[j], j});
            }
        }
    }
    
    if (dist[n] == INF) return -1;
    else return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, -1, sizeof g);
    
    while (m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        
        add(a, b, w);
    }
    
    printf("%d", Dijkstra());
    return 0;
}

🎞️Bellman-Ford

上图要求0点到其余点的最短距离，用Dijkstra算法可以吗？

Dijkstrakiller

可以看到Dijkstra这种贪心算法是完全失效了，第一次加入S集合的节点本来距离就应该确定了，但是有负权边时，会被继续更新。有负权边时，就应该把任务交给下面要介绍的Bellman-Ford算法了。

🍟有边数限制的最短路

🍬原题链接：有边数限制的最短路

🪅算法思想：

Bellman-Ford算法，带负权边单源最短路算法，时间复杂度为 $O (nm)$ （顶点数*边数），本质上就是一个无脑遍历边的算法，所以边的存储不做要求，只要能遍历到全部边就可以，可以用结构体，也可以用邻接表等。

注意：Bellman-Ford算法可以求带负权边的最短路径，但是如果一个图中有负权回路，最短路径则不一定存在。

上图中，2、3、4号节点形成了一个环，如果要求1号节点到5号节点距离的最小值，可以走 1-2-3-4-3-5，总权值为3，也可以走 1-2-3-4-3-4-2-3-5，总权值为2。以此类推，可以无限走这个环，在没有路径边数的限制下，最小值为负无穷。

所以，Bellman-Ford算法可以用来求从起始点到终点的最多经过 k条边的最短距离，也可以用来判断负环（一般用SPFA算法判断，不用这个算法）。

具体做法：循环k次，每次遍历全部的边，按照 dist[b] = min(dist[b], dist[a] + w) 更新b点到1号节点的距离即可。

与Dijkstra算法演示的例子相同：

对应的Bellman-Ford算法的动画演示如下：

Bellman

🪆代码实现：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

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

int n, m, k;
int dist[N], bkup[N]; // bkup是dist的备份，每次必须使用备份遍历，否则会出现更新顺序影响结果的情况

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < k; ++i)
    {
        // 每次必须用上一次更新完的值进行更新，如果直接用dist数组进行更新，会出现
        // 如果有3->1，2->3这两条边，k为1，如果先遍历到3->1这条边，dist[3]被更新，下面遍历2->3这条边，dist[2]也会被更新
        // 但是2节点到1节点必须要走两条边，不满足题意，所以每次必须用上一次更新完的值进行更新
        memcpy(bkup, dist, sizeof dist);
        for (int j = 0; j < m; ++j)
        {
            auto& e = edges[j];
            dist[e.b] = min(dist[e.b], bkup[e.a] + e.w);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 0; i < m; ++i)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    
    
    bellman_ford();
    
    if (dist[n] > INF / 2) printf("impossible"); // 这里要注意，由于有负权边dist[a] = INF , dist[b] = INF, a->b w = -1时，dist[b] = INF - 1，小于INF，所以这里判断是否在一个区间
    else printf("%d", dist[n]);
    return 0;
}

🎟️SPFA

下面来看一个例子：

上面这个图，如果按照Bellman-Ford算法做，每次循环只有一次更新是有效的，其余全都是无效循环，大大浪费了时间。

Bellmankiller

我们发现，只有上一轮被更新过的节点，这一轮才会以该节点为出发点继续更新，所以能不能存储上一轮更新过的节点，这一轮直接遍历这些节点的出边，不就能大大减少无效的循环了吗？

🌭SPFA求最短路

🍬原题链接：SPFA求最短路

🪅算法思想：

SPFA算法，带负权单源最短路算法，时间复杂度一般为 $O (m)$ ，最坏为 $O (nm)$ ，本算法优化了Bellman-Ford算法每次遍历全部边的过程，本质上是 BFS ，边的存储结构为 邻接矩阵。

核心思路：只有 dist[a] 更新了， a->b 边才会被使用，否则不会使用a->b这条边，所以本算法存储更新过的最短路，很像Dijkstra堆优化版本。
具体做法：
1. 初始化dist数组， $d i s t [1] = 0$ ，将1号节点其入队。
2. 广度优先搜索，出队节点元素，遍历每个节点的出边，更新，直到队列为空。

SPFA算法动画演示：

SPFA

🪆代码实现：

// SPFA
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N], e[N], ne[N], val[N], idx;
int dist[N];
bool book[N]; // 标记是否在队列中

int SPFA()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    book[1] = true;
    
    while (q.size())
    {
        int u = q.front();
        q.pop();
        
        // 出队列以后记得更新状态
        book[u] = false;
        
        for (int i = g[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[u] + val[i] < dist[j])
            {
                dist[j] = dist[u] + val[i];
                // 防止重复添加
                if (!book[j])
                {
                    q.push(j);
                    book[j] = true;
                }
            }
        }
    }
    
    return dist[n];
}

void add(int a, int b, int w)
{
    e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, -1, sizeof g); // g必须在add函数前更新
    for (int i = 0; i < m; ++i)
    {
        int a, b ,w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
    }
    
    int ret = SPFA();
    if (ret == INF) puts("impossible");
    else printf("%d
", ret);
    return 0;
}

🍿SPFA判断负环

🍬原题链接：spfa判断负环

🪅算法思想：

核心思想：设置一个cnt数组用来存储1号点到其他点路径中边的数量，使用SPFA算法进行更新，如果到一个节点到1号节点路径中边的数量 $c n t [i] >= n$ ，说明路径中出现环，如果出现环，一定是负环，因为正环不会 $d i s t [i] + 环的路径 <= d i s t [i]$ 也就不会被更新。

如何证明 $c n t [i] >= n$ 就一定出现环呢？

反证法，如果 $c n t [i] >= n$ 没有环，说明从1到 i 没有走过任何一个重复的节点，但是一共只有n个节点，当有n条边时，连接了n+1个节点，根据抽屉原理，必定有相同的节点，所以必定有环。

🪆代码实现：

// SPFA
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N], e[N], ne[N], val[N], idx;
int dist[N], cnt[N];
bool book[N];

bool SPFA()
{
    // 由于本题目只是用来判断负环，dist数组不表示最短距离，可以不需要初始化，这样更新的就只有负权边了
    queue<int> q;
    
    // 将全部节点入队，这里没有说是连通图，所以必须全部点先入队列
    for (int i = 1; i <= n; ++i)
    {
        q.push(i);
        book[i] = true;
    }
    
    while (q.size())
    {
        int u = q.front();
        q.pop();
        
        // 出队列以后记得更新状态
        book[u] = false;
        
        for (int i = g[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[u] + val[i] < dist[j])
            {
                dist[j] = dist[u] + val[i];
                cnt[j] = cnt[u] + 1; // 路径更新
                
                if (cnt[j] >= n) return true;
                // 防止重复添加
                if (!book[j])
                {
                    q.push(j);
                    book[j] = true;
                }
            }
        }
    }
    
    return false;
}

void add(int a, int b, int w)
{
    e[idx] = b, val[idx] = w, ne[idx] = g[a], g[a] = idx++;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, -1, sizeof g); // g必须在add函数前更新
    for (int i = 0; i < m; ++i)
    {
        int a, b ,w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
    }
    
    if (SPFA()) puts("Yes");
    else puts("No");
    return 0;
}

🎫Floyd

🧂Floyd求最短路

🍬原题链接：Floyd求最短路

🪅算法思想：

Floyd算法，多源最短路算法（一次可以求出所有节点到其他节点的最短路，有无负权边皆可使用），时间复杂度为 $O(n^3)$ ，本质上是区间动态规划，核心代码只有四行，非常牛。边的存储结构：邻接矩阵。

状态： $f [i, j, k]$ 表示从 $i$ 走到 $j$ 的路径上除了 $i$ 和 $j$ 以外只经过 $1 \sim k$ 号节点的所有路径的最短距离。eg. $f [5, 6, 3]$ 表示从 $5$ 号节点走到 $6$ 号节点只经过 $1 ， 2 ， 3$ 这三个节点的最短距离
最初状态： $f [i, j, k] = \infty$
状态转移方程： $f [i, j, k] = min (f [i, j, k], f [i, k, k - 1] + f [k, j, k - 1])$ ， $i$ 节点到 $j$ 节点只经过 $1 \sim k$ 号节点的最短距离等于本身原值和 $i$ 节点到 $k$ 节点只经过 $1 \sim k - 1$ 号节点最短距离和 $k$ 节点到j节点只经过 $1 \sim k - 1$ 号节点最短距离之和的最小值。

由于状态转移中，k层状态只需要用到k-1层状态，所以k这一维可以被优化掉。

🪆代码实现：

// Floyd算法
#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n, m, q;

int g[N][N];

void Floyd()
{
    // 在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层
    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()
{
    scanf("%d%d%d", &n, &m, &q);
    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;
    
    while (m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = min(g[a][b], w);
    }
    
    Floyd();
    
    while (q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (g[a][b] > INF / 2) puts("impossible");
        else printf("%d
", g[a][b]);
    }
    return 0;
}

📙后记

最后总结一下上面所有算法：

单源最短路算法
- 朴素Dijkstra：贪心算法，必须保证无负权边，适合稠密图，时间复杂度为 $O(n^2)$ （n为节点个数），对于边的存储结构为 邻接矩阵。
- 堆优化Dijkstra：贪心算法，必须保证无负权边，适用于稀疏图，时间复杂度为 $O (m l o g n)$ （m为边数，n为节点数），边的存储结构为邻接表。
- Bellman-Ford：循环遍历，时间复杂度为 $O (nm)$ （顶点数*边数），所以边的存储不做要求，只要能遍历到全部边就可以，可以用结构体，也可以用邻接表等。
- SPFA：BFS，时间复杂度一般为 $O (m)$ ，最坏为 $O (nm)$ ，边的存储结构为 邻接矩阵。
多元最短路算法
- Floyd：动态规划，时间复杂度为 $O(n^3)$ ，边的存储结构为邻接矩阵。

如果解析有不对之处还请指正，我会尽快修改，多谢大家的包容。

如果大家喜欢这个系列，还请大家多多支持啦😋！

如果这篇文章有帮到你，还请给我一个大拇指 👍和小星星 ⭐️支持一下白晨吧！喜欢白晨【算法】系列的话，不如关注👀白晨，以便看到最新更新哟！！！

我是不太能熬夜的白晨，我们下篇文章见。

猜你喜欢

Jease 2.6发布 Java开源内容框架
EasyCVR对接华为iVS订阅摄像机和用户变更请求接口介绍
JVM调优总结：反思
【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
JVM调优总结：调优方法
前端面试【JavaScript】— typeof 是否能正确判断类型？
JVM调优总结：新一代的垃圾回收算法
前端面试【JavaScript】— instanceof 能否判断基本数据类型？
JVM调优总结：典型配置举例
前端面试【JavaScript】— 能不能手动实现一下 instanceof 的功能？
前端面试【JavaScript】— Object.is和=== 有什么区别？
JVM调优总结：分代垃圾回收详述
前端面试【JavaScript】— JS中类型转换有哪几种？
WPF开发入门尝试
前端面试【JavaScript】— == 和 ===有什么区别？
一个Java程序员对2011年的回顾
前端面试【JavaScript】— 对象转原始类型是根据什么流程运行的？
JVM调优总结：垃圾回收面临的问题
直接在代码里面对list集合进行分页
JVM调优总结：基本垃圾回收算法

zl程序教程

当前栏目

【算法】最短路算法

文章目录

📗前言

📘最短路算法

🎗️Dijkstra

🍕朴素Dijkstra算法

🍔堆优化Dijkstra算法

🎞️Bellman-Ford

🍟有边数限制的最短路

🎟️SPFA

🌭SPFA求最短路

🍿SPFA判断负环

🎫Floyd

🧂Floyd求最短路

📙后记

相关文章