Spfa
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; }