浅谈spfa与dijkstra的区别

· · 算法·理论

也许有初学者与我这个蒟蒻一样，对着模板搞不清spfa和dijkstra的区别

真就只是 _priorityqueue 和 queue 吗？

确实，spfa和dijkstra的核心都是松弛操作，即打擂台;

if(dist[v]>dist[u]+graph[u][v])
{
    dist[v]=dist[u]+graph[u][v];
}

但彼此之间写法还是有区别的，比如说：

spfa只使用一个struct存邻接表，dijkstra还有个额外的node，定义如下：

struct node
{
    int dis;
    int to;//表示通向哪个点
}

显而易见，该结构体维护一条边

不同的queue，spfa存的是点，dijkstra存的是边

我们重新回顾dijkstra的算法：

我们先将dist[起点]置为0，其余dist置为正无穷

然后选取dist最小的一个点（这显然给堆优准备了条件）

尝试松弛所有以它为起点的边

每松弛成功，下一次松弛就以该边终点为起点

显然我们要设立一个vis[]给点打访问标记

当所有vis都为true时，无法松弛，结束循环。

而spfa就不一样了，他关心的是：

哪些点是松弛的candidators

所以我们push的自然是点了！而且也不对点做特殊要求，自然queue即可满足需要了！

简单来说，spfa和dijkstra都是贪心，但实现中，你可以粗暴地理解为spfa是“每次确定一个点”，dijkstra是“每次确定一条边”。

所以spfa会把每个点的每条边跑一遍，自然很容易卡到O(nm)

dijkstra关心的是边，每个点会作为起点枚一次（外层循环），再作为终点枚一次（内层循环）。所以不加优化的情况下就是O（n^2），堆优化即用O(logn)找终点，总共O（nlogn）。

这里给出P3371（spfa实现）和P4779（dijkstra实现）的AC code，仅供算法比较使用！

//P3371
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=4.5e+7;

struct edge
{
    int to;
    int last;
    int val;
};
edge e[maxm];
int head[maxn];
int vis[maxn];
int dist[maxn];
queue<int>q;
int tot=0;

inline void adde(int a,int b,int c)
{
    e[++tot].last=head[a];
    e[tot].to=b;
    e[tot].val=c;
    head[a]=tot;
}

void spfa(int n,int x=1)
{
    memset(dist,0x3f,sizeof(dist));
    q.push(x);
    dist[x]=0;
    vis[x]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]--;
        for(int i=head[u];i!=0;i=e[i].last)
        {
            int v=e[i].to;
            if(dist[v]>dist[u]+e[i].val)
            {
                dist[v]=dist[u]+e[i].val;
                //cnt[i]=cnt[u]+1;
                //if(cnt[i]>=n)return false;
                if(!vis[v])
                {
                    vis[v]++;
                    q.push(v);
                }
            }
        }
    }
    //return true;
}

int main()
{
    int n=0,m=0,s=1;
    cin>>n>>m>>s;
    //build(n,m);
    int a=0,b=0,c=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        adde(a,b,c);
    }
    spfa(n,s);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==0x3f3f3f3f)
        {
            cout<<2147483647;
            if(i<n)cout<<' ';
            continue;
        }
        cout<<dist[i];
        if(i<n)cout<<' ';
    }
    return 0;
}
//P4779
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=2e5+7;

struct edge
{
    int to;
    int last;
    int val;
};

struct node
{
    int dis;
    int s;

    friend bool operator <(node a,node b)
    {
        return a.dis>b.dis;
    }
};
edge e[maxm*2];
int head[maxn];
int vis[maxn];
int dist[maxn];
priority_queue<node>q;
int tot=0;

inline void adde(int a,int b,int c)
{
    e[++tot].last=head[a];
    e[tot].to=b;
    e[tot].val=c;
    head[a]=tot;
}

void dijkstra(int n,int x=1)
{
    memset(dist,0x3f,sizeof(dist));
    q.push({0,x});
    dist[x]=0;
    vis[x]=1;
    while(!q.empty())
    {
        int u=q.top().s;
        q.pop();
        vis[u]--;
        for(int i=head[u];i!=0;i=e[i].last)
        {
            int v=e[i].to;
            if(dist[v]>dist[u]+e[i].val)
            {
                dist[v]=dist[u]+e[i].val;
                if(!vis[v])
                {
                    vis[v]++;
                    q.push({dist[v],v});
                }
            }
        }
    }
}

int main()
{
    int n=0,m=0,s=1;
    cin>>n>>m>>s;
    int a=0,b=0,c=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        adde(a,b,c);
    }
    dijkstra(n,s);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==0x3f3f3f3f)
        {
            cout<<2147483647;
            if(i<n)cout<<' ';
            continue;
        }
        cout<<dist[i];
        if(i<n)cout<<' ';
    }
    return 0;
}