SPFA算法详解

这篇具有很好参考价值的文章主要介绍了SPFA算法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

什么是SPFA算法

SPFA 算法是Bellman-ford算法的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环

前置知识:Bellman-ford算法详解_真的没事鸭的博客-CSDN博客

SPFA算法思路

SPFA算法其实就是在Bellman-ford算法基础上的优化。Bellman-ford算法看起来比较傻,每次迭代的话是遍历所有边来更新,但是每次迭代的话不是每条边都会更新。SPFA算法就是对这个做优化,每次迭代dist[b]可以更新的话,一定是dist[a]变小了,因为如果dist[a]不变的话,dist[b]一定不变。只有dist[a]变小了,它的后继才会变小。所以SPFA算法就从这个点进行优化。

SPFA算法的思路就是迭代的时候用一个队列来做,队列里面存的就是到起点距离变小的点。先把起点放到队列里面去,只要队列不空,也就是队列里面还有距离变小的点的话,就执行一下操作:

  1. 先取出队头t,然后队头出队
  2. 更新t的所有出边,t到起点的距离不是变小了吗, 那么所有和t相连的点都有可能变小,如果更新成功的话,就入队。但是注意要判断一下这个点已经入过队的话就不用重复加入了。

补充

SPFA算法的时间复杂度一般是O(m),最坏情况下时O(nm)。一般正权图我们是用Dijkstra算法去做,但是其实大部分的正权图的问题都可以用SPFA算法来做。不过出题人卡复杂度的话可能就用不了。所以SPFA算法是由Bellman-ford算法优化来的,不过长得特别像Dijkstra算法。

案例

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

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

如果路径不存在,则输出 impossible

数据范围

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

输入样例:

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

输出样例:

2

来源:ACWing

 思路

这个和Dijkstra堆优化版的代码相似,就是用队列优化了一下。文章来源地址https://www.toymoban.com/news/detail-422195.html

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e6+10;
int h[N],e[N],ne[N],idx,w[N];//邻接表,w数组表示权重,idx是两个点之间的桥梁
int n,m;
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++;
}
int spfa()
{
    //初始化距离,1号点距离为0
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    //初始一个队列,用来存距离变小的点
    queue<int>q;
    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])//判断是否在队中,不在的话入队
                {
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}
int main()
{
    cin>>n>>m;
    //初始化h数组
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        //这里不考虑重边
        add(a,b,c);
    }
    if(spfa()==0x3f3f3f3f)
    cout<<"impossible";
    else
    cout<<spfa();
    return 0;
}

到了这里,关于SPFA算法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图搜索算法详解 - DFS、BFS、Bellman-Ford、Dijkstra

    图搜索算法是许多应用程序的基础,例如社交网络分析、路径规划、数据挖掘和推荐系统。在本文中,我们将深入探讨图搜索算法的世界,探索它们的定义、重要性和实际应用。 图搜索算法是一种用于遍历图的技术,图是由 关系 连接的 节点集合 。在社交网络、网页或生物

    2024年02月16日
    浏览(42)
  • 最短路之 Bellman-ford 算法

    若有向图有n个点,m条边 。 扫描所有边,对每条边进行一次松弛(即对a,b为端点 , 权重为w的边,dist[b] = min(dist[a] , dist[a] + w )) 重复此流程(最多重复n次)直到没有更新操作发生 给你一张 n 个顶点 m 条边的有向简单图,顶点编号从 1 到 n,每条边都有一个边权,边权为非

    2024年02月17日
    浏览(40)
  • Bellman-ford 贝尔曼-福特算法

    Bellman-ford算法可以解决负权图的单源最短路径问题 --- 它的优点是可以解决有负权边的单源最短路径问题, 而且可以判断是否负权回路 它也有明显的缺点,它的时间复杂度O(N*E)(N是点数 , E是边数)普遍是要高于Dijkstra算法O(N^2)的,像这里,我们使用邻接矩阵实现,那

    2024年02月06日
    浏览(44)
  • 图论详解——Bellman-Ford(清晰易懂)

    开学第一周,晚上属实作业有点乱 于是就拖更了一周 今天我们来讲解一下图论最短路径算法中 最简单 最清晰易懂 同时时间复杂度最高的算法 它的时间复杂度能达到O(VE)(点的数量*边的数量) 在学习Bellman-Ford之前,你需要先学会链式前向星 大家可以上网或者其他途径自行

    2024年02月06日
    浏览(44)
  • 最短路径算法 | Bellman-Ford Algorithm

    我们在之前的文章中已经讨论了最短路径算法中最经典的Dijkstra‘s Algorithm。然而,Dijkstra\\\'s Algorithm虽然好用,却仍然存在一些缺点即无法解决带有负权重路线的问题,改进后的Dijkstra算法尽管可以解决一些简单的负权重问题,但仍然无法解决带有负循环的图的最短路径问题。

    2024年02月08日
    浏览(51)
  • 图论最短路径——Bellman-Ford Algorithm算法

    在图论中,寻找最短路径是一个常见且重要的问题。对于这个问题,有许多算法可以解决,其中最著名的是 Dijkstra 算法。然而,当图中包含负权边时,Dijkstra 算法可能无法正确工作。这时,贝尔曼-福特(Bellman-Ford)算法就派上了用场。 贝尔曼-福特算法可以在含有负权边的图

    2024年04月27日
    浏览(38)
  • 图论14-最短路径-Dijkstra算法+Bellman-Ford算法+Floyed算法

    https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapter11_Min_Path 2.4.1 判断某个顶点的连通性 2.4.2 求源点s到某个顶点的最短路径 存放节点编号和距离 这里的缺点就是,更新node时候,会重复添加节点相同的node,但是路径值不一样。不影响最后结果。 更新pre数组 输出路径 初始化两

    2024年02月04日
    浏览(35)
  • Bellman-Ford-贝尔曼-福特-算法求最短路-负环

    Bellman-Ford(贝尔曼-福特)算法基于松弛操作的单源最短路算法。 e[u]存u点的出边的邻点和边权,d[u]存u点到源点的距离。 初始化,ds]=0,d[其它点]=+o; 执行多轮循环。每轮循环,对所有边都尝试进行一次松弛操作; 当一轮循环中没有成功的松弛操作时,算法停止 为什么最坏需要

    2024年02月13日
    浏览(38)
  • 最短路问题 Bellman-Ford(单源最短路径)(图解)

    对于边(u,v),用dist(u)和(u,v)的和尝试更新dist(v):                          dist(v) = min(dist(v) , dist(u)+l(u,v) 注:dist(i)为源点(起点)到i点的距离,l(u,v)为u-v的边权。 Bellman-Ford的基本操作是进行多次迭代,每一轮迭代对图上所有边进行松弛操作,直到

    2024年02月09日
    浏览(38)
  • 图论:最短路(dijkstra算法、bellman算法、spfa算法、floyd算法)详细版

    终于是学完了,这个最短路我学了好几天,当然也学了别的算法啦,也是非常的累啊。 话不多说下面看看最短路问题吧。 最短路问题是有向图,要求的是图中一个点到起点的距离,其中我们要输入点和点之间的距离,来求最短路。 下面分为几类题目: 单源汇最短路--一个起

    2024年01月21日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包