SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)，但是一般情况下他的复杂度还是很优秀的，为O(mn)，其中稀疏图中m约等于2，稠密图...关于SPFA：他死了，n为边数（值得一提，有的非常bt的数据会故意卡spfa不让你过 比如菊花图，蒲公英图什么的）
算法大意：设立一个队列来保存所有待优化的结点，先初始化所有最短路径，然后从起点开始不断遍历每一条边，不断进行松弛操作，再用已经优化完的结点去更新队列中其他节点
重要变量解释：
dis表示从源点到点i的最短路径
vis表示这个点目前是否在队列里
head表示这个点所有出边中序号最大的那一条
代码：
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<time.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-;
ll pp=;
ll mo(ll a,ll pp){if(a>= && a<pp)return a;a%=pp;if(a<)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=;for(;b;b>>=,a=mo(a*a,pp))if(b&)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=;
char last=' ',ch=getchar();
while(ch<'' || ch>'')last=ch,ch=getchar();
while(ch>='' && ch<='')ans=ans*+ch-'',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
//head const int inf=;
int n,m,s;//点的个数、有向边的个数、出发点的编号
int dis[],vis[],head[],cnt;
//dis表示从源点到点i的最短路径
//vis表示这个点目前是否在队列里
//head表示这个点所有出边中序号最大的那一条 struct Edge
{
int next,dis,to;
}edge[]; queue <int> q; inline void add_edge(int from,int to,int dis)
{
cnt++;
edge[cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}//存边 void spfa()
{
rep(i,,n)
dis[i]=inf,vis[i]=;//初始化
dis[s]=;
vis[s]=;//把始点标记成在队列中
q.push(s);//入队
while(!q.empty())
{
int u=q.front();//队首的点
q.pop();//出队
vis[u]=;//标记成已经出队
for(int i=head[u];i;i=edge[i].next)//遍历每一条边
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;//松弛操作
if(!vis[v])
{
q.push(v);
vis[v]=;
}//入队
}
}
}
} int main()
{
scanf("%d %d %d",&n,&m,&s);
for(int i=;i<=m;++i)
{
int u,v,d;//第i条有向边的出发点、目标点和长度
scanf("%d %d %d",&u,&v,&d);
add_edge(u,v,d);
}
spfa();
for(int i=;i<=n;++i)
{
if(i==s) printf("0 ");//自己到自己为0
else printf("%d ",dis[i]);
}
return ;
}
感觉和Dijkstra差不多，但其实他俩区别还是很大的
Dijkstra是找到从当前节点所有出边中找到最短的，然后用这条最短边继续更新其他路径
而SPFA是对当前节点的所有出边不断进行松弛操作，然后用更新完的边去更新其他结点的其他边
（其实好像挺像的）