SPFA及SLF优化-白红宇

SPFA及SLF优化

阅读量：5072 次

发布时间：2019-06-12

本文共 1766 字，大约阅读时间需要 5 分钟。

算法简介

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。

算法流程

SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，算法大致流程是用一个队列来进行维护，即用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。当队列不为空时，取出队首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列queue 和一个指示顶点是否在队列中的标记数组mark。为了方便查找某个顶点的邻接点，图采用邻接表存储。

判断负权回路的方案很多，世间流传最广、比较容易实现并且高效的方法的是记录每个结点进队次数，大于等于|V|次表示有负权。

两个著名优化（SLF和LLL）：

SPFA 是按照 FIFO 的原则更新距离的, 没有考虑到距离标号的作用. 实现中 SPFA 有两个非常著名的优化: SLF 和 LLL.

　　SLF: Small Label First 策略. （比较常用）

　　实现方法是, 设队首元素为 , 队列中要加入节点 , 在时加到队首而不是队尾, 否则和普通的 SPFA 一样加到队尾.

　　LLL: Large Label Last 策略. （不太常用）

　　实现方法是, 设队列中的队首元素为 , 距离标号的平均值为 , 每次出队时, 若 , 把移到队列末尾, 如此反复, 直到找到一个使 , 将其出队.

C++模版：(没加SLF优化)

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define arraysize 501int maxData = 0x7fffffff;typedef struct edge{ int to; int w;}edge;vector
                      
                        adjmap[arraysize]; //vector实现邻接表 int d[arraysize];bool final[arraysize]; //记录顶点是否在队列中，SPFA算法可以入队列多次 int cnt[arraysize]; //记录顶点入队列次数 bool SPFA(int s){ queue
                       
                         myqueue; int i,j; for(i=0;i
                        
                         d[topint]+ adjmap[topint][i].w) { d[to] = d[topint]+ adjmap[topint][i].w; if(!final[to]) { final[to] = true; cnt[to]++; if(cnt[to]>=n) //当一个点入队的次数>=n时就证明出现了负环。 return true; myqueue.push(to); } } } } return false;}int main(){ for(i=1;i
                         
                          >s>>e>>w; temp.to = e; temp.w = w; adjmap[s].push_back(temp); temp.to = s; adjmap[e].push_back(temp); }}

转载于:https://www.cnblogs.com/AbandonZHANG/archive/2012/08/12/4113956.html

你可能感兴趣的文章