SPFA算法模板题题解&学习笔记
1 学习笔记
1.1 算法介绍
SPFA是一种单源最短路算法,可以用来算带负环的最短路,是bellman_ford算法的优化
1.2 算法流程
SPFA是用了广搜进行优化,有点类似深搜里的剪枝(个人认为)
我们首先需要一个数组dist,保存每个点的最小点权。
然后用类似广搜的方法,开始遍历图:
while(!q.empty())
{
int f=q.front();
q.pop();
int tt=v[f].size();//我用的是邻接表
for(int i=0;i<tt;i++)
{
...
}
}
然后像bellman_ford算法里面,遇到最小值就更新
for(int i=0;i<tt;i++)
{
int tmp=v[f][i];
if(dist[tmp]>dist[f]+w[f][i])
{
dist[tmp]=dist[f]+w[f][i];//w数组是用来表示边权的
}
}
然后,像 有边数限制的最短路 题目中的 题解里一样,因为预防出现题目中直接更新到n的办法,需要打标记。与bellman_ford算法不同的是,他只需要将已经放入队列的点标上标记就好了,这样只要不是开始更新当前点的相邻点,其他的点就自然不会更新此数,这也是广搜特性的体现——层次遍历,如图:
所以核心代码如下:
while(!q.empty())
{
int f=q.front();
q.pop();
st[f]=false;//已经轮到当前节点遍历了,所以可以撤销
int tt=v[f].size();//我用的是邻接表
for(int i=0;i<tt;i++)
{
int tmp=v[f][i];
if(dist[tmp]>dist[f]+w[f][i])
{
dist[tmp]=dist[f]+w[f][i];//w数组是用来表示边权的
if(!st[tmp])
{
q.push(tmp);
st[tmp]=true;//打上标记
}
}
}
模板题题解
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<int> v[N],w[N];
int dist[N];
int n,m;
bool st[N];
int spfa()
{
queue<int> q;
q.push(1);
st[1]=true;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
while(!q.empty())
{
int f=q.front();
q.pop();
st[f]=false;
int tt=v[f].size();
for(int i=0;i<tt;i++)
{
int tmp=v[f][i];
if(dist[tmp]>dist[f]+w[f][i])
{
dist[tmp]=dist[f]+w[f][i];
if(!st[tmp])
{
q.push(tmp);
st[tmp]=true;
}
}
}
}
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0;i<m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
v[x].push_back(y);
w[x].push_back(z);
}
int t=spfa();
if(t==0x3f3f3f3f) puts("impossible");//不能使用-1,因为万一答案就是-1,那就GG了
else printf("%d",t);
}
希望大家喜欢,同时有什么说的不对的欢迎指出来