是  的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)，但是一般情况下他的复杂度还是很优秀的，为O(mn)，其中稀疏图中m约等于2，稠密图...关于SPFA：他死了，n为边数（值得一提，有的非常bt的数据会故意卡spfa不让你过   比如菊花图，蒲公英图什么的）

 

算法大意：设立一个队列来保存所有待优化的结点，先初始化所有最短路径，然后从起点开始不断遍历每一条边，不断进行松弛操作，再用已经优化完的结点去更新队列中其他节点

 

重要变量解释：

dis表示从源点到点i的最短路径

vis表示这个点目前是否在队列里

head表示这个点所有出边中序号最大的那一条

 

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long ll;typedef long double ld;typedef pair
               
                 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 secondld eps=1e-9;ll pp=1000000007;ll mo(ll a,ll pp){ if(a>=0 && a
                
                 >=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 
                 
                   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是对当前节点的所有出边不断进行松弛操作，然后用更新完的边去更新其他结点的其他边

（其实好像挺像的）