SPFA的优化

【为什么要优化】

关于SPFA，他死了（懂的都懂）

进入正题。。。

一般来说，我们有三种优化方法。

SLF优化：

SLF优化，即 Small Label First 策略，使用双端队列进行优化。

一般可以优化15%~20%，在竞赛中比较常用。

设从 u 扩展出了 v ，队列中队首元素为 k ，若 dis[ v ] < dis[ k ] ，则将 v 插入队首，否则插入队尾。

注：队列为空时直接插入队尾。

 deque<int> q;

 inline void spfa(int x)

 {

     memset(d,0x3f,sizeof(d));

     memset(v,,sizeof(v));

     d[x]=;v[x]=;

     q.push_back(x);

     while(q.size())

     {

         int index=q.front();q.pop_front();

         v[index]=;

         for(int i=head[index];i;i=g[i].next){

             int y=g[i].ver,z=g[i].edge;

             if(d[y]>d[index]+z){

                 d[y]=d[index]+z;

                 if(!v[y]){

                     if(!q.empty()&&d[y]>=d[q.front()]) q.push_back(y);

                     else q.push_front(y);

                     v[y]=;

                 }

             }

         }

     }

 }

LLL优化：

LLL优化，即 Large Label Last 策略，使用双端队列进行优化。

一般用SLF+LLL可以优化50%左右，但是在竞赛中并不常用LLL优化。（所以我就懒得写了，这是从这个大佬那里嫖来的）

设队首元素为 k ，每次松弛时进行判断，队列中所有 dis 值的平均值为 x 。

若 dist[ k ] > x ，则将 k 插入到队尾，查找下一元素，直到找到某一个 k 使得 dis[ k ] <= x ，则将 k 出队进行松弛操作。

 void spfa(){

     int u,v,num=;

     long long x=;

     list<int> q;

     for(int i=;i<=n;i++){path[i]=MAX;vis[i]=false;}

     path[s]=;

     vis[s]=true;

     q.push_back(s);

     num++;

     while(!q.empty()){

         u=q.front();

         q.pop_front();

         num--;x-=path[u];

         while(num&&path[u]>x/num){

             q.push_back(u);

             u=q.front();

             q.pop_front();

         }

         vis[u]=false;

         for(int i=head[u];i;i=a[i].next){

             v=a[i].to;

             if(relax(u,v,a[i].w)&&!vis[v]){

                 vis[v]=true;

                 if(!q.empty()&&path[v]<path[q.front()])q.push_front(v);

                 else q.push_back(v);

                 num++;x+=path[v];

             }

         }

     }

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

     printf("\n");

 }

DFS优化：

这种优化顾名思义，就是用dfs的思想代替bfs的思想来优化Bellman-Ford。

常常用于判断正/负环，时间复杂度可以达到O(m)（m是边）。思路是，我们每一次dfs的时候如果走回之前dfs过的点，那就是有环，除了这个dfs的标记，我们还可以打另一个vis数组记录更新过权值的节点，以后就不必重复更新，大大降低复杂度。

不过如果无环的话，那还是上面那两种优化稍微适用一点。代码比较短，但是不好扩展。

 inline bool spfa(int x)

 {

     dfs[x]=;

     for(int i=head[x];i;i=g[i].next)

     {

         int y=g[i].ver,z=g[i].edge;

         if(!v[y]||d[y]<d[x]+z){

             if(dfs[y]) return ;

             v[y]=;

             d[y]=d[x]+z;

             if(!spfa(y)) return ;

         }

     }

     dfs[x]=;

     return ;

 }

巴特西

SPFA的优化

【为什么要优化】

最新文章

热门文章