图论：SPFA算法

发布于：2025-08-01 ⋅ 阅读:(22) ⋅ 点赞:(0)

Bellman_ford 队列优化算法 ，也叫SPFA算法，相对于贝尔曼-福德算法来说，SPFA用了队列进行优化，省去了一些多余的操作，本文会介绍一下基本的SPFA算法在例题中的应用以及对模板的整理，有需要的小伙伴可以保存起来。

SFPA（Algorithm for Shortest Path According to Flowing Priority）是一种单源最短路算法，它可以在边权有负值的情况下，找到从源节点到其他节点的最短路径。

大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。

但真正有效的松弛，是基于已经计算过的节点在做的松弛。

只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。 

SFPA算法的核心思想是根据节点的流动优先级来选择拓展的顺序，具体流程如下：

初始化：创建一个优先队列和一个标记数组，用来存储每个节点的最短距离和是否已经找到最短路径。

将源节点加入优先队列，并标记为已访问，设置源节点的最短距离为0。

重复以下步骤直到优先队列为空： a. 从优先队列中取出流动最大优先级的节点u。 b. 遍历节点u的所有邻居节点v，更新v的最短距离：

如果从u到v的路径长度加上边(u,v)的权值小于v的最短距离，则更新v的最短距离，并将v加入优先队列。 c. 标记节点u为已访问。
完成之后，最短路径的结果可以从标记数组中获得。

经典例题：

SPFA在算法竞赛中的应用 

SPFA（Shortest Path Faster Algorithm）本质上是Bellman-Ford算法的队列优化版本，特别适合解决带负权边的单源最短路径问题。

何时选择SPFA？

  1. 必须使用SPFA的情况：

    • 图中存在负权边（Dijkstra无法处理）

    • 需要检测负权环（如差分约束系统）

  2. 推荐使用SPFA的情况：

    • 稀疏图（边数E ≈ 顶点数V）

    • 需要频繁更新最短路径（如动态图）

  3. 避免使用SPFA的情况：

    • 稠密图（边数E接近V²）

    • 确定没有负权边（直接用Dijkstra）

    • 题目数据刻意卡SPFA（如网格图）

赛时易踩坑点：

  1. 常见坑点：

    • 忘记初始化dis数组为INF

    • 没有清空队列和inQueue数组（多组数据时）

    • 把无向图当成有向图处理（少加反向边）

四大路径算法的对比：

算法 时间复杂度 可否处理负权边 可否检测负权环 适用场景
Dijkstra O((V+E)logV) 否 否 无负权边的稀疏/稠密图
堆优化Dijkstra O((V+E)logV) 否 否 无负权边的大规模图
Bellman-Ford O(VE) 是 是 小规模图带负权边
SPFA O(VE)~O(E) 是 是 稀疏图带负权边

路径问题三剑客：

学完最小生成树、堆优化版Dijkstra以及SPFA之后脑子更加迷糊了有没有，感觉都差不多但是又分不清哪个是哪个具体写的时候又不会，下面简单总结一下三者之间的关系。

一、核心使命

算法 核心任务 结果性质
最小生成树(Prim/Kruskal) 用最小成本连接所有点 形成一棵树（无环）
堆优化Dijkstra 找到单源点到其他点的最短路径 形成最短路径树
SPFA 带负权边的最短路径/检测负权环 可能包含负权环

形象理解：MST（最小生成树）是规划全城电网的最经济方案，Dijkstra是导航软件找最快路线，SPFA是考虑"倒贴钱"路线的导航 

二、联系与区别速查

对比维度 最小生成树 堆优化Dijkstra SPFA
数据结构 优先堆/并查集 优先堆 普通队列
边权要求 无方向性 必须非负 可正可负
时间复杂度 O(ElogV) O(ElogV) 最差O(VE)平均O(E)
是否成环 绝对无环 可能隐含环 可能显式含负权环
典型应用 网络布线 导航最短路径 含负权的最短路问题

三、实战中的选择策略

        当题目出现以下关键词时：

  • "连接所有节点"、"最小总成本" → 最小生成树

  • "最短路径"、"最少时间"、且无负权 → 堆优化Dijkstra

  • "可能盈利的路径"、"检测负权环" → SPFA

记住这三者的核心区别：MST关注全局连接成本，Dijkstra追求单源最短路径，SPFA解决含负权的特殊场景。

城市间货物运输I

题目链接：城市间货物运输

这道题用贝尔曼福德算法也是可以通过的，但是这里是用的SPFA来加深对这个算法的印象，首先就是需要用邻接表来存图，因为每一次都需要对这个点所连接的点进行遍历，而且还需要有一个数组用于标记当前的点是否在队列中，所以就从起点开始，每次将已经达到切不在队列中的点入队，然后在取出以上一次为基础再进行松弛操作，基于上述思路就有了一下代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 10;
vector<pii> e[N];
vector<int> ans(N,inf);
vector<bool> f(N,false);
queue<int> q;
int n,m;

void solve()
{
	cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    int start = 1,end = n;
    q.push(start);ans[start] = 0;
    while(!q.empty())
    {
        int index = q.front();q.pop();
        f[index] = false;
        for(auto &i : e[index])
        {
            int from = index;
            int to = i.fi;
            int value = i.se;
            if(ans[to] > ans[from] + value)
            {
                ans[to] = ans[from] + value;
                if(!f[to])
                {
                    f[to] = true;
                    q.push(to);
                }
            }
        }
    }
    if(ans[end] == inf) cout<<"unconnected"<<endl;
    else cout<<ans[end]<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}

signed main()// Don't forget pre_handle!
{
	IOS
	int T=1;
//	cin>>T;
	while(T--) solve(); 
	return 0;
}

依旧将模板整理如下：

图论的SPFA算法模板，XCPCer可拿~

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 10;
vector<pii> e[N];    // 邻接表存图 e[u] = {v, w}
vector<int> ans(N,inf);  // 存储起点到各点的最短距离
vector<bool> f(N,false); // 标记顶点是否在队列中
queue<int> q;        // 用于优化的队列
int n,m;            // 顶点数，边数

void solve()
{
    cin>>n>>m;
    
    // 初始化
    for(int i=0;i<=n;i++)
    {
        e[i].clear();
        ans[i]=inf;
        f[i]=false;
    }
    while(!q.empty()) q.pop();
    
    // 建图
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        // 如果是无向图，添加反向边
        // e[v].push_back({u,w});
    }
    
    int start = 1, end = n; // 默认起点1，终点n
    ans[start] = 0;
    q.push(start);
    f[start] = true;
    
    // SPFA主过程
    while(!q.empty())
    {
        int index = q.front();
        q.pop();
        f[index] = false;
        
        for(auto &i : e[index])
        {
            int to = i.fi;
            int value = i.se;
            
            // 松弛操作
            if(ans[to] > ans[index] + value)
            {
                ans[to] = ans[index] + value;
                
                // 如果目标顶点不在队列中，加入队列
                if(!f[to])
                {
                    q.push(to);
                    f[to] = true;
                }
            }
        }
    }
    
    // 输出结果
    if(ans[end] == inf)
    {
        cout<<"unconnected"<<endl; // 不可达
    }
    else
    {
        cout<<ans[end]<<endl;     // 输出最短距离
    }
}

signed main()
{
    IOS
    int T=1;
    // cin>>T;  // 多组数据时取消注释
    while(T--)
    {
        solve();
    }
    return 0;
}

【模板】负环 

题目链接：【模板】负环

这道题是SPFA的板子题，对负环的判断有多种方式，可以统计这个点所连接的边数，也可以统计这个点入队的次数，如果超过了n-1就说明构成了负环，因为最短路最多有n-1条边。

方法 1

在 SPFA 算法的基础上，我们再添加一个统计每个结点入队次数的数组。
如果一个点入队超过了 n 次（即图上结点个数），则判断有负环。

方法 2

我们统计每两个点间的最短路包含多少条边，如果在一条最短路上包含超过了 (n−1) 条边，说明有边被重复使用，则判断有负环。

// Problem: P3385 【模板】负环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3385
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 10;
vector<pii> e[N];
vector<bool> f(N,false);
vector<int> cnt(N,0),ans(N,inf);

void init()
{
	fill(ans.begin(),ans.end(),inf);
	fill(f.begin(),f.end(),false);
	fill(cnt.begin(),cnt.end(),0);
	for(int i=0;i<N;i++) e[i].clear();
}
int n,m;

void solve()
{
	queue<int> q;
	init();//别忘记初始化！
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;cin>>u>>v>>w;
		e[u].push_back({v,w});
		if(w>=0) e[v].push_back({u,w});
	}
	int start = 1;
	q.push(start);
	f[start] = true;
	ans[start] = 0;//千万别忘记！！！！！！！！！！！！！！！！！！！！！！！！
	while(!q.empty())
	{
		int index = q.front();
		q.pop();//这个也不能忘记！！！！！！
		f[index] = false;
		for(auto &i : e[index])
		{
			int to = i.fi;
			int value = i.se;
			if(ans[to] > ans[index] + value)
			{
				ans[to] = ans[index] + value;
				if(!f[to])
				{
					f[to] = true;
					q.push(to);
					cnt[to]++;
					if(cnt[to] >= n)
					{
						cout<<"YES"<<endl;
						return ;
					}
				}
			}
		}
	}
	cout<<"NO"<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}

signed main()// Don't forget pre_handle!
{
	IOS
	int T=1;
	cin>>T;
	while(T--) solve(); 
	return 0;
}

城市间货物运输II

题目链接：城市间货物运输II

这道题和上面的类似，就是增加了一个对负环的判断，不再过多解释，代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e3+10;
vector<int> ans(N,inf);//别忘记初始化
vector<pii> e[N];
vector<bool> inq(N,false);
vector<int> cnt(N,0);
queue<int> q;
int n,m;

void solve()
{
	cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    int start = 1,end = n;
    ans[start] = 0;
    q.push(start);
    inq[start] = true;
    while(!q.empty())
    {
        int index = q.front();
        q.pop();
        inq[index] = false;
        for(auto &i : e[index])
        {
            int to = i.fi;
            int value = i.se;
            if(ans[to] > ans[index] + value)
            {
                ans[to] = ans[index] + value;
                if(!inq[to])
                {
                    q.push(to);
                    inq[to] = true;
                    cnt[to]++;
                    if(cnt[to] >= n)
                    {
                        cout<<"circle"<<endl;
                        return ;
                    }
                }
            }
        }
    }
    if(ans[end] == inf) cout<<"unconnected"<<endl;
    else cout<<ans[end]<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}

signed main()// Don't forget pre_handle!
{
	IOS
	int T=1;
//	cin>>T;
	while(T--) solve(); 
	return 0;
}

队列优化版Bellman_ford 的时间复杂度 并不稳定，效率高低依赖于图的结构。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布