当前位置:首页 » 《随便一记》 » 正文

【最短路算法】第三弹:一文学懂spfa 算法(队列优化的Bellman-Ford算法)

26 人参与  2023年05月04日 16:25  分类 : 《随便一记》  评论

点击全文阅读


在这里插入图片描述

博主简介:努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。博主主页: @是瑶瑶子啦所属专栏: 算法 ;该专栏专注于蓝桥杯和ACM等算法竞赛?近期目标:写好专栏的每一篇文章

在这里插入图片描述

?前言

前面,我们分别介绍了Dijkstra算法(【最短路算法】一篇文章彻底弄懂Dijkstra算法|多图解+代码详解)和Bellman-Ford算法
【最短路算法】第二弹:一文弄懂Bellman-Ford(贝尔曼福特算法)
前者用于求单源、正权边最短路问题,后者用于求单源、带负权边最短路问题。通过对Bellman-Ford算法讲解,我们知道,Bellman-Ford算法美中不足的一点在于时间复杂度是O(nm),时间复杂度过高。

今天,我们学习的spfa算法,优化了Bellman-Ford算法,时间复杂度 平均情况下 O(m),最坏情况下 O(nm), n 表示点数,m 表示边数。

目录

?前言?一、算法思想?二、spfa求最短路?三、spfa判断负权回路

?一、算法思想

在讲具体算法思想之前,我们来仔细探讨一下,优化的点在哪里?

Bellman-ford算法慢,就慢在,其实在后面遍历时,每次迭代都要遍历所有边。前面我们说到过,迭代次数代表从源点出发,经过不超过迭代次数的边数,所经过的顶点的dist都是准确的,确定的。但是在后面迭代中,又重复去遍历这些边,其实是没有必要的。

因为判断一个点的松驰条件为:假设边为a→bdist[b] = min (dist[b], dist[a]+w),当dist[a](a其实不是某一个点,代表的是从a指向b的边的一群顶点)都一直没有更新,dist[b]当然也不会更新,确定好了dist[b],在后面遍历中,dist[b] = min (dist[b], dist[a]+w)完全没有必要进行。那如何减少这一无意义操作呢?

核心就是,我们只对其dist有更新的顶点进行松驰!(注意,这样一来,spfa当然就不会有bellman-Ford算法的那种迭代次数的意义存在!)

spfa,利用宽搜思想,使用队列为数据结构,优化了这一点。,优化了这一点。

?首先,将dist变小的即有被更新的点入队(因为它的更新,一般会带来其他点的更新)

?取出队列元素,并将其弹出

?对该元素的出边元素进行遍历&松驰

?如果有元素松驰成功(dist更新,也就是变小了),那么该元素也入队

算法模板如下:(from acWing)

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

?二、spfa求最短路

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 31 2 52 3 -31 3 4

输出样例:

2
#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int N = 100010;int n,m;int h[N],w[N],e[N],ne[N],idx;//邻接表存储图int dist[N];bool st[N];//标记节点是否在队列中//构建边void add(int a,int b, int c){    e[idx] = b,w[idx] = c, ne[idx] = h[a],h[a] = idx++;}void spfa(){    memset(dist, 0x3f, sizeof(dist));    dist[1] = 0;        queue<int> q;//队列    q.push(1);//因为dist[1] 从0x3f3f3f3f松驰为了0,加入队列    st[1] = true;        while(q.size()){//while队列不空        int t = q.front();//取出队头元素,由该点更新其出边点                q.pop();//出队                st[t] = false;                //遍历t点的出边点        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;                }            }        }            }}int main(){    scanf("%d%d",&n,&m);        //!h[N]数组要先初始化        memset(h,-1,sizeof(h));        for(int i = 0; i < m; i++){        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        add(a,b,c);    }        spfa();        if(dist[n] == 0x3f3f3f3f) puts("impossible");    else printf("%d\n",dist[n]);    return 0;}

?三、spfa判断负权回路

spfa判断负环

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

如果图中存在负权回路,则输出 Yes,否则输出 No

数据范围

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

?思路
统计当前每个点的最短路中所包含的边数,如果某点的最短路所包含的边数大于等于n,则也说明存在负环

1、dist[x] 记录虚拟源点到x的最短距离

2、cnt[x] 记录当前x点到虚拟源点最短路的边数,初始每个点到虚拟源点的距离为0,只要他能再走n步,即cnt[x] >= n,则表示该图中一定存在负环,由于从虚拟源点到x至少经过n条边时,则说明图中至少有n + 1个点,表示一定有点是重复使用

3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少,因此进行对该点j进行更新,并且对应cnt[j] = cnt[t] + 1,往前走一步

?详细注释题解

#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int N = 2010, M = 10010;int n,m;int h[N],w[M],e[M],ne[M],idx;int dist[N],cnt[N];bool st[N];void add(int a,int b,int c){    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++; }//spfa算法判断负权回路bool spfa(){      queue<int> q;    //将所有顶点都入队    for(int i = 1; i <= n; i ++){        st[i] = true;        q.push(i);    }    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];                cnt[j] = cnt[t] + 1;                if (cnt[j] >= n) return true;                if (!st[j])                {                    q.push(j);                    st[j] = true;                }            }        }    }    return false;}int main(){        scanf("%d%d",&n,&m);        memset(h,-1,sizeof(h));        while(m --){                int a, b, c;        scanf("%d%d%d",&a,&b,&c);        add(a,b,c);    }    if(spfa()) puts("Yes");    else puts("No");        return 0;}

?注意点

为什么不用初始化dist[N]? 因为负环的存在,所以即使每个点距离虚拟原点距离为0,负权回路的存在就可以更新某个点的dist为更小的值.这题是判断,只要有这个变小(松驰)趋势就Ok,并不是求最短路注意:该题是判断是否存在负环,并非判断是否存在从1开始的负环,因此需要将所有的点都加入队列中,更新周围的点.换句话来说,**从哪个点出发并不重要,重要的是是否有负环!**一定要将所有点入队我认为是因为图可能会不连通,如果负环是在和1这个点不连通的部分(可能图中存在负环,但是从一号点到不了),就无法查到,所以要将所有点都入队!遍历所有点,肯定能遍历到有负环的回路,只要有负环,dist就会更新,顶点就会接着入队,cnt也接着增加!对比:以 S 点为源点跑 Bellman-Ford 算法时,如果没有给出存在负环的结果,只能说明从 S 点出发不能抵达一个负环,而不能说明图上不存在负环。

在这里插入图片描述

Java岛冒险记【从小白到大佬之路】
LeetCode每日一题–进击大厂算法

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/60734.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1