Spfa

2019-09-17 09:53:13来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

原文链接:https://www.cnblogs.com/LengYun/p/11460428.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:2019秋季PAT甲级_C++题解

下一篇:从“杨辉三角形”谈起