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(-1); #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-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} ll read(){ ll ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } //head const int inf=2147483647; int n,m,s;//点的个数、有向边的个数、出发点的编号 int dis[10005],vis[10005],head[10005],cnt; //dis表示从源点到点i的最短路径 //vis表示这个点目前是否在队列里 //head表示这个点所有出边中序号最大的那一条 struct Edge { int next,dis,to; }edge[9999999]; 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,1,n) dis[i]=inf,vis[i]=0;//初始化 dis[s]=0; vis[s]=1;//把始点标记成在队列中 q.push(s);//入队 while(!q.empty()) { int u=q.front();//队首的点 q.pop();//出队 vis[u]=0;//标记成已经出队 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]=1; }//入队 } } } } int main() { scanf("%d %d %d",&n,&m,&s); for(int i=1;i<=m;++i) { int u,v,d;//第i条有向边的出发点、目标点和长度 scanf("%d %d %d",&u,&v,&d); add_edge(u,v,d); } spfa(); for(int i=1;i<=n;++i) { if(i==s) printf("0 ");//自己到自己为0 else printf("%d ",dis[i]); } return 0; }
感觉和Dijkstra差不多，但其实他俩区别还是很大的
Dijkstra是找到从当前节点所有出边中找到最短的，然后用这条最短边继续更新其他路径
而SPFA是对当前节点的所有出边不断进行松弛操作，然后用更新完的边去更新其他结点的其他边
（其实好像挺像的）