首页 > 其他分享 >SPFA

SPFA

时间:2024-05-12 21:09:01浏览次数:15  
标签:dist int tt hh st 队列 SPFA

这算是我的第一篇使用LaTeX的文章
易写,支持负权,可判负环,可以求最短路,也可以最长路,什么都行。就是容易被卡qwq
所以SPFA他死了。是Bellman_Ford算法的队列优化版。

使用范围

支持负权,可以处理负环,可判负环,可以求最短路,也可以求最长路。
平均时间复杂度 \(O(m)\),极限时间复杂度为 \(O(nm)\) 即退化成 Bellman_Ford。
如上面所说,容易被卡成 \(O(nm)\) 的时间复杂度。

中心思想

其算法正确性来自 Bellman_Ford 算法。

观察 Bellman_Ford 算法,可以发现,实际上只有上次被松弛的点,才能有可能引起下次操作中边的松弛,于是可以用一个队列,存入“可能引起下次松弛的点”,只利用这里面的点即可。

值得注意的是,这个队列中的点不需要重复,它并没有意义,所以对于上面所说的点,我们要判断是否在队列之内。

代码

给出两种代码,一种手写循环队列,一种用 SLT 队列。

如果不用 STL 队列,一定要手写队列,因为一个点可能会入队多次,如果不循环,可能会出界。因此手写要用循环队列。是手写还是直接 STL 就看个人习惯了。

值得一说的特性,因为 \(st\) 数组内存的是每个点是否进队,而当 SPFA 结束时,队列里一定没有点,因此 \(st\) 数组全为空。

循环队列

int spfa(int S, int T)
{
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
    int tt = 0, hh = 0;
    q[tt ++ ] = S;
    dist[S] = 0;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        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[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return dist[T];
}

STL 队列

int spfa(int S, int T)
{
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	queue<int> q;
	q.push(S);
	dist[S] = 0; 
	st[S] = true; // 这句话可有可无,毕竟入队之后直接就 st[t] = false; 了
	
	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] == 0)
			    {
			        st[j] = true;
			        q.push(j);
			    }
			}
		} 
	}
	return dist[T];
}

扩展

  1. SPFA判断负环

标签:dist,int,tt,hh,st,队列,SPFA
From: https://www.cnblogs.com/blind5883/p/18188178

相关文章

  • SPFA算法
    单源最短路算法,可以处理负边权,平均时间复杂度\(O(kn)\),最坏时间复杂度\(O(mn)\)问题描述:有一个连通图\(G=(V,E)\),连接节点\(i\)和节点\(j\)的边权写作\(e^i_j\)(\(e^i_j\geq0\)),求从起点(\(s,s\inV\))开始,到其它各个节点(\(d,d\inV-s\))的最短路长度。思路详解:设从起点s到节点d......
  • 最短路算法(Dijkstra + SPFA + Floyd)
    最短路算法(Dijkstra+SPFA+Floyd)Dijkstra算法1.算法基本介绍Dijkstra算法通常是求解单源最短路中最快的算法,但它无法处理存在负权边的情况(原因在正确性证明中)。Dijkstra本质上是一种贪心算法,通过不断调整每个点的“当前距离”最终得到最优结果,其实后面要讲到的几种算法也大......
  • 【学习笔记】spfa
    一、spfa模板:voidspfa(intx){ for(inti=1;i<=n;i++) vis[i]=0,dis[i]=inf; dis[1]=0,f[1]=1; q.push(1); while(!q.empty()) { intt=q.front(); q.pop(); vis[t]=0; for(inti=first[t];i;i=e[i].next) { intto=e[i].to; if(dis[t]+e[i].v<......
  • spfa优化
    \(spfa\)的优化都是基于\(deque\)的,我们通常使用\(LLL\)优化,代码简单,优化效果最好,详情可见参考这里,例题可以参考这里1.\(LLL\)优化(入队优化)LargeLabelLast优化:思路就是将\(dist\)更大的点放入队尾,将\(dist\)更小的点放入队头,优先使用\(dist\)更小的点进行松弛操......
  • 关于spfa
    “正常”求最短路BFS版本voidspfa(){queue<int>q;q.push(0);fl[0]=1;while(q.size()){intx=q.front(); q.pop(); fl[x]=0; for(inti=h[x];i;i=s[i].next){ inty=s[i].to; if(dis[y]<dis[x]+s[i].w){ ......
  • spfa优化
    1.SLF优化在我们学SPFA的时候,要把每一个入队的点插入到队尾,可是有些时候这个点作为队尾没有作为队头效率高,因为这个点有时放在队首就能直接用,那么什么样的点作为队首更好呢?当然是dis值越小越可能刷新其它\(dis\)值,所以对比当前元素与对首元素的\(dis\)值,如果当前元素的\(dis......
  • SPFA算法
    一、单源最短路径typedeflonglongll;constintMAX=2e3+5;constllINF=numeric_limits<ll>::max();typedefstruct{ intto,worth;}edge;intn,m;vector<edge>G[MAX];lld[MAX];boolvis[MAX];voidspfa(ints){ fill(d+1,d+1+n,......
  • SPFA最短路
    目录从Bellman-Ford开始核心思想模拟算法执行过程时间复杂度模板spfaspfa优化的思想模板从Bellman-Ford开始对于所有边权都大于等于0的图,任意两个顶点之间的最短路,显然不会经过重复的顶点或者边。也就是说任意一条最短路经过的定点数不会超过n个,边不会超过n-1条边而对于有边权......
  • 通信(二分+SPFA好题)
    第1题    通信查看测评数据信息某城市有N座通信基站,P条双向电缆,第i条电缆连接基站Ai和Bi。特别地,1号基站是通信公司的总站,N号基站位于一座农场中。现在,农场主希望对通信线路进行升级,其中升级第i条电缆需要花费Li。电话公司正在举行优惠活动。农场主可以指定......
  • spfa 详解
    算法基础 模板题 第1题    spfa最短路练习查看测评数据信息给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。数据保证不存在负权回路。1≤n,m≤100000......