spfa

　　(spfa) 算法的全称是： (shortest) (path) (faster) (algorithm) ，是 (bellman-ford) 算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。

基本原理

　　设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点 (u) ，并且用结点 (u) 当前的最短路径估计值对离开结点 (u) 所指向的结点 (v) 进行松弛操作，即判断是否有 (dis[v]＞dis[u]＋w) （ (w) 是连接 (u) 与 (v) 的边的长度），若有，则更新 (dis[v]) 。如果结点 (v) 的最短路径估计值有所调整，且结点 (v) 不在当前的队列中，就将结点 (v) 放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
　　(spfa) 在形式上和 (bfs) 非常类似，不同的是 (bfs) 中一个结点出了队列就不可能重新进入队列，但是 (spfa) 中一个结点可能在出队列之后再次被放入队列，也就是一个结点改进过其它的结点之后，过了一段时间可能本身被改进，于是再次将其加入队列，再次用来改进其它的结点。
　　每次将结点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个结点 (v) 的最短路径估计值 (dis[v]) 变小。所以算法的执行会使 (dis) 越来越小。若图中不存在负权环，则每个结点都有最短路径值。因此，算法不会无限执行下去，随着 (dis) 值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。
　　如果一个结点进入队列达到 (n) 次，则表明图中存在负权环，没有最短路径。

效率分析

　　在随机图中， (spfa) 的期望时间复杂度为 (o(ke)) ，其中 (k) 是常数，代表所有结点的平均入队次数（一般 (k≤2) ）， (e) 是边数。但往往因为出题人所造的毒瘤数据而被卡，导致复杂度退化为 (o(ve)) ，其中 (v) 是结点数。

核心代码

ll n,m,s,cnt,head[maxn],dis[maxn]; bool vis[maxn]; struct edge{ll u,v,w,next;}edge[maxm]; void add(ll u,ll v,ll w)                    /*链式前向星存图*/ {     edge[++cnt].u=u;     edge[cnt].v=v;     edge[cnt].w=w;     edge[cnt].next=head[u];     head[u]=cnt; } queue<ll>q; void spfa() {     for(ll i=1;i<=n;i++)dis[i]=inf;         /*初始距离设为inf*/     dis[s]=0;     q.push(s);                              /*源点入队*/     vis[s]=1;     while(!q.empty())     {         ll u=q.front();                     /*队首元素出队*/         q.pop();         vis[u]=0;         for(ll i=head[u];i;i=edge[i].next)  /*寻找与所有以队首 u 为起点的边*/         {             ll v=edge[i].v,w=edge[i].w;             if(dis[v]>dis[u]+w)             {                 dis[v]=dis[u]+w;            /*松弛操作*/                 if(!vis[v])                 /*若终点 v 不在队列中*/                 {                     q.push(v);              /*入队*/                     vis[v]=1;                 }             }         }     } }

例题解析

洛谷 p3371 【模板】单源最短路径（弱化版）

　　给出一个有向图 (g＝＜v,e＞) ，一个源点 (s) ，求点 (s) 到图中所有点的最短距离。

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define maxn 10005 #define maxm 500005 #define inf 2147483647 template<class t>inline void read(t &x) {     x=0;register char c=getchar();register bool f=0;     while(!isdigit(c))f^=c=='-',c=getchar();     while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();     if(f)x=-x; } template<class t>inline void print(t x) {     if(x<0)putchar('-'),x=-x;     if(x>9)print(x/10);     putchar('0'+x%10); } template<class t>inline void print(t x,char c){print(x),putchar(c);} ll n,m,s,cnt,head[maxn],dis[maxn]; bool vis[maxn]; struct edge{ll u,v,w,next;}edge[maxm]; void add(ll u,ll v,ll w) {     edge[++cnt].u=u;     edge[cnt].v=v;     edge[cnt].w=w;     edge[cnt].next=head[u];     head[u]=cnt; } queue<ll>q; void spfa() {     for(ll i=1;i<=n;i++)dis[i]=inf;     dis[s]=0;     q.push(s);     vis[s]=1;     while(!q.empty())     {         ll u=q.front();         q.pop();         vis[u]=0;         for(ll i=head[u];i;i=edge[i].next)         {             ll v=edge[i].v,w=edge[i].w;             if(dis[v]>dis[u]+w)             {                 dis[v]=dis[u]+w;                 if(!vis[v])                 {                     q.push(v);                     vis[v]=1;                 }             }         }     } } int main() {     read(n),read(m),read(s);     ll u,v,w;     for(ll i=1;i<=m;i++)     {         read(u),read(v),read(w);         add(u,v,w);     }     spfa();     for(ll i=1;i<=n;i++)print(dis[i],' ');     return 0; }