dij-spfa乱搞

以前见过一篇另类堆优化dij的题解，然而找不到了

那位作者称它为dij-spfa（大概是这个意思，然而确实很形象

这方法比较玄学，正确性没有严格证出来，然而对拍是验证猜想的最好途径

不过也可能并不玄学，只是我一时没想出来而已，如果有见解可以发在评论

还有一个关于这个的讨论帖

众所周知，dij堆优的代码是这样，用了STL：

#include<bits/stdc++.h>

#define LL long long

using namespace std;

struct node{

    int w;

    LL v;

    bool operator < (const node& x) const{

        return v>x.v;

    }

};

int n,m,s;

LL dis[100006],vis[100006];

int fir[100006],nex[200006],to[200006],v[200006];

priority_queue<node>q;

void dij(){

    memset(dis,0x3f,sizeof dis);

    dis[s]=0;

    q.push((node){s,0});

    while(q.size()){

        int u=q.top().w;q.pop();

        if(vis[u]) continue;

        vis[u]=1;

        for(int i=fir[u];i;i=nex[i]){

            int vv=to[i];

            if(dis[vv]>dis[u]+v[i]){

                dis[vv]=dis[u]+v[i];

                q.push((node){vv,dis[vv]});

            }

        }

    }

}

int main(){

    scanf("%d%d%d",&n,&m,&s);

    for(int i=1;i<=m;i++){

        int x,y,z;scanf("%d%d%d",&x,&y,&z);

        to[i]=y;v[i]=z;

        nex[i]=fir[x];

        fir[x]=i;

    }

    dij();

    for(int i=1;i<=n;i++) printf("%lld ",dis[i]);

}

思考一下这个重载运算符：

struct node{

    int w;

    LL v;

    bool operator < (const node& x) const{

        return v>x.v;

    }

};

和这个入队操作：

if(dis[vv]>dis[u]+v[i]){

    dis[vv]=dis[u]+v[i];

    q.push((node){vv,dis[vv]});

}

每次入队，都是把节点编号和当前节点距离做成结构体

然而，在这个结构体在优先队列的期间，这个\(dis\)的值可能会变（被松弛了），然而这并不影响结构体里的值

那么，我们可不可以只让节点号入队，然后比较节点的\(dis\)

然后，再结合一点spfa，给每个点记录是否在队中，如果在，就只松弛不入队

那么稍加改动可以写出这样的代码，当然这里我优先队列是手写堆实现的，\(vis\)记录的是是否在对中：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<stack>

#include<iomanip>

#include<cstring>

#define R register

#define LL long long

inline int read(){

    int x=0,y=1;

    char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-') y=-1;

        c=getchar();

    }

    while(c>='0'&&c<='9'){

        x=x*10+(c^48);

        c=getchar();

    }

    return x*y;

}

int n,m,s;

int to[200006],net[200006],v[200006];

int tot;

int fir[100006],dis[100006];

bool vis[100006];

int dui[100006],sz;

void swapn(int &ii,int &jj){

    ii^=jj;

    jj^=ii;

    ii^=jj;

}

int minnpop(){

    int res=dui[1];

    dui[1]=dui[sz];

    dui[sz]=0;

    sz--;

    int i=1,L,r;

    while(i*2<=sz){

        L=i*2;

        r=L+1;

        if(r<=sz&&dis[dui[r]]<dis[dui[L]]) L=r;

        if(dis[dui[i]]<=dis[dui[L]]) break;

        swapn(dui[i],dui[L]);

        i=L;

    }

    return res;

}

void add(int x){

    dui[++sz]=x;

    int i=sz,p;

    while(i>1){

        p=i/2;

        if(dis[dui[p]]<=dis[dui[i]]) break;

        swapn(dui[p],dui[i]);

        i=p;

    }

}

void dijkstra(){

    memset(dis,66,sizeof(dis));

    dis[s]=0;

    add(s);

    vis[s]=true;

    int st,now;

    while(sz){

        st=minnpop();

        vis[st]=false;

        for(R int i=fir[st];i;i=net[i]){

            now=to[i];

            if(dis[now]>dis[st]+v[i]){

                dis[now]=dis[st]+v[i];

                if(!vis[now]){

                    add(now);

                    vis[now]=true;

                }

            }

        }

    }

}

int main(){

    n=read();

    m=read();

    s=read();

    int sta,e;

    for(R int i=1;i<=m;i++){

        sta=read();

        e=read();

        v[++tot]=read();

        to[tot]=e;

        net[tot]=fir[sta];

        fir[sta]=tot;

    }

    dijkstra();

    for(R int i=1;i<=n;i++) printf("%d ",dis[i]);

    return 0;

}

这种方法看似很乱搞，其实是能过的

为什么说他乱搞？因为可以看出：

if(dis[dui[p]]<=dis[dui[i]]) break;

这是堆操作的代码，我们\(dui\)数组存的是节点编号，比较规则是比较当期节点的\(dis\)

然而，每经过一次松弛，\(dis\)都会变，但此时我们并不会刻意去调整堆结构

所以堆就乱了

那么它为啥还能过？个人认为是：在频繁的push和pop中，恰好将堆的性质调整好了

因为只有目前不在堆中的节点才能入堆，所以堆中元素最多\(n\)个，让堆操作的复杂度大大减小，可能也是因为元素少了，堆性质更容易维护才使这个算法没有挂掉

回想一下第一种，只要当前节点被松弛了，就接着扔到堆里，之后每个节点只能被用来松弛其它节点一次，已经被用过的话就直接扔掉

但这个是，只要堆里有节点，不管它有没有别用去松驰过，都继续用它松弛（spfa的影子）

可能，除了堆操作以外的正确性，就是用这一点来保证的

目前，用这种方法写最短路的题，还没有挂掉过

并且，经过了@Nickel_Angel大佬的几百次\(n \leq 1000,m \leq 10^5\)的对拍，也没挂，并且感谢她，当时发那个讨论帖的时候我还不会对拍

而且，它更快！

普通版，800ms+

优化后，200ms+

用时是之前的四分之一

主要节省时间的地方，应该就是刚才说的堆的复杂度降低

而且在洛谷标准版最短路这样卡spfa的数据下，dij-spfa能跑出这样的时间，说明这个算法在用时上也是比较稳定

然而我用这个方法去做bzoj的那个需要用斐波那契堆或配对堆优化的dij，还是不能过

最后，最前面两个完整代码是我去年写的，后面那个是刚写，看起来不大一样

如果您有hack数据，或者严谨的证明，欢迎在评论区给出，感谢

巴特西

dij-spfa乱搞

最新文章

热门文章