SPFA算法详解

现在是2016年4月21日,今天我学习了不少奇奇怪怪的算法,同时还为我的博客增加了mathJax支持。此文是一篇关于SPFA算法的归纳,部分内容转载,不喜勿喷

适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路,即最短路径一定存在。当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。

算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止

 

期望的时间复杂度O(ke), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2。

 

实现方法:

  建立一个队列,初始时队列里只有起始点,再建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)。然后执行松弛操作,用队列里有的点作为起始点去刷新到所有点的最短路,如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

判断有无负环:

  如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)

 



 

 

 

首先建立起始点a到其余各点的

最短路径表格

                                 

首先源点a入队,当队列非空时:

 1、队首元素(a)出队,对以a为起始点的所有边的终点依次进行松弛操作(此处有b,c,d三个点),此时路径表格状态为:

                                 

在松弛时三个点的最短路径估值变小了,而这些点队列中都没有出现,这些点

需要入队,此时,队列中新入队了三个结点b,c,d

队首元素b点出队,对以b为起始点的所有边的终点依次进行松弛操作(此处只有e点),此时路径表格状态为:

                                

在最短路径表中,e的最短路径估值也变小了,e在队列中不存在,因此e也要

入队,此时队列中的元素为c,d,e

队首元素c点出队,对以c为起始点的所有边的终点依次进行松弛操作(此处有e,f两个点),此时路径表格状态为:

                                

在最短路径表中,e,f的最短路径估值变小了,e在队列中存在,f不存在。因此

e不用入队了,f要入队,此时队列中的元素为d,e,f

 队首元素d点出队,对以d为起始点的所有边的终点依次进行松弛操作(此处只有g这个点),此时路径表格状态为:

 

 

                              

在最短路径表中,g的最短路径估值没有变小(松弛不成功),没有新结点入队,队列中元素为f,g

队首元素f点出队,对以f为起始点的所有边的终点依次进行松弛操作(此处有d,e,g三个点),此时路径表格状态为:



                               

在最短路径表中,e,g的最短路径估值又变小,队列中无e点,e入队,队列中存在g这个点,g不用入队,此时队列中元素为g,e

队首元素g点出队,对以g为起始点的所有边的终点依次进行松弛操作(此处只有b点),此时路径表格状态为:

                          

在最短路径表中,b的最短路径估值又变小,队列中无b点,b入队,此时队列中元素为e,b

队首元素e点出队,对以e为起始点的所有边的终点依次进行松弛操作(此处只有g这个点),此时路径表格状态为:

 

                         

在最短路径表中,g的最短路径估值没变化(松弛不成功),此时队列中元素为b

队首元素b点出队,对以b为起始点的所有边的终点依次进行松弛操作(此处只有e这个点),此时路径表格状态为:

                        

在最短路径表中,e的最短路径估值没变化(松弛不成功),此时队列为空了

最终a到g的最短路径为14

 

 

program:

#include<cstdio>

using namespace std;

struct node

{int x;

 int value;

 int next;

};

node e[60000];

int visited[1505],dis[1505],st[1505],queue[1000];

int main()

{

  int n,m,u,v,w,start,h,r,cur;

  freopen(“c.in”,”r”,stdin);

  freopen(“c.out”,”w”,stdout);

  while(scanf(“%d%d”,&n,&m)!=EOF)

  {

    for(int i=1;i<=1500;i++)

      {visited[i]=0;

       dis[i]=-1;

       st[i]=-1;  //这个初始化给下边那个while循环带来影响

      }

 

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

      {

       scanf(“%d%d%d\n”,&u,&v,&w);    

       e[i].x=v;            //记录后继节点    相当于链表中的创建一个节点,并使得数据域先记录

       e[i].value=w;

       e[i].next=st[u];     //记录顶点节点的某一个边表节点的下标,相当于在链表中吧该边表节点的next指针先指向他的后继边表节点

       st[u]=i;                //把该顶点的指针指向边表节点,相当于链表中的插入中,头结点的指针改变

      }

    start=1;

    visited[start]=1;

    dis[start]=0;

    h=0;

    r=1;

    queue[r]=start;

    while(h!=r)

     {

      h=(h+1)%1000;

      cur=queue[h];

      int tmp=st[cur];

      visited[cur]=0;

    

     while(tmp!=-1)

        {

            if (dis[e[tmp].x]<dis[cur]+e[tmp].value)            //改成大于号才对

            {

                   dis[e[tmp].x]=dis[cur]+e[tmp].value;

                    if(visited[e[tmp].x]==0)

                      {

                           visited[e[tmp].x]=1;

                           r=(r+1)%1000;

                            queue[r]=e[tmp].x;

                       }

            }

         tmp=e[tmp].next;     

        }

     }

    printf(“%d\n”,dis[n]);

  }

  return 0;  

}



 

                     (没有质量,就出数量)  下面一文转载出处:http://blog.csdn.net/morgan_xww/article/details/6279596

  1. /
  2. SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表]
  3. 是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。
  4. 算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素,
  5. 并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。
  6. 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
  7. SPFA 在形式上和BFS非常类似,不同的是BFS中一个点出了队列就不可能重新进入队列,但是SPFA中
  8. 一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本
  9. 身被改进,于是再次用来改进其它的点,这样反复迭代下去。
  10. 判断有无负环:如果某个点进入队列的次数超过V次则存在负环(SPFA无法处理带负环的图)。
  11. SPFA算法有两个优化算法 SLF 和 LLL:
  12. SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,
  13. 否则插入队尾。
  14. LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入
  15. 到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。
  16. 引用网上资料,SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。
  17. 在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。
  18.  
  19. //用数组实现邻接表存储,pnt[i,0]表示与i相邻的结点个数,pnt[i,1…k]存储与i相邻的点 
  20. int  pnt[MAXN][MAXN]; 
  21. int  map[MAXN][MAXN];
    //map[i,j]为初始输入的i到j的距离,并且map[i,i]=0;未知的map[i,j]=INF; 
  22. int  dis[MAXN]; 
  23. char vst[MAXN]; 
  24.  
  25. int SPFA(int n,int s) 
  26.     int i, pri, end, p, t; 
  27.     memset(vst, 0, sizeof(vst)); 
  28.     for (i=1; i<=n; i++) 
  29.         dis[i] = INF; 
  30.     dis[s] = 0; 
  31.     vst[s] = 1; 
  32.     Q[0] = s; pri = 0; end = 1; 
  33.     while (pri < end) 
  34.     { 
  35.         p = Q[pri]; 
  36.         for (i=1; i<=pnt[p][0]; i++) 
  37.         { 
  38.             t = pnt[p][i]; 
  39.             //先释放,释放成功后再判断是否要加入队列 
  40.             if (dis[p]+map[p][t] < dis[t]) 
  41.             { 
  42.                 dis[t] = dis[p]+map[p][t]; 
  43.                 if (!vst[t]) 
  44.                 { 
  45.                     Q[end++] = t; 
  46.                     vst[t] = 1; 
  47.                 } 
  48.             } 
  49.         } 
  50.         vst[p] = 0; 
  51.         pri++; 
  52.     } 
  53.     return 1; 

    1. / 
    2. SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表] 
    3. 是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。 
    4. 算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素, 
    5. 并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。 
    6. 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。 
    7.  
    8. SPFA 在形式上和BFS非常类似,不同的是BFS中一个点出了队列就不可能重新进入队列,但是SPFA中 
    9. 一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本 
    10. 身被改进,于是再次用来改进其它的点,这样反复迭代下去。 
    11.  
    12. 判断有无负环:如果某个点进入队列的次数超过V次则存在负环(SPFA无法处理带负环的图)。 
    13.  
    14. SPFA算法有两个优化算法 SLF 和 LLL: 
    15. SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首, 
    16. 否则插入队尾。 
    17. LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入 
    18. 到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。 
    19. 引用网上资料,SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。 
    20. 在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。 
    21. /  
    22.   
    23. //用数组实现邻接表存储,pnt[i,0]表示与i相邻的结点个数,pnt[i,1…k]存储与i相邻的点  
    24. int  pnt[MAXN][MAXN];  
    25. int  map[MAXN][MAXN]; //map[i,j]为初始输入的i到j的距离,并且map[i,i]=0;未知的map[i,j]=INF;  
    26. int  dis[MAXN];  
    27. char vst[MAXN];  
    28.   
    29. int SPFA(int n, int s)  
    30. {  
    31.     int i, pri, end, p, t;  
    32.     memset(vst, 0, sizeof(vst));  
    33.     for (i=1; i<=n; i++)  
    34.         dis[i] = INF;  
    35.     dis[s] = 0;  
    36.     vst[s] = 1;  
    37.     Q[0] = s; pri = 0; end = 1;  
    38.     while (pri < end)  
    39.     {  
    40.         p = Q[pri];  
    41.         for (i=1; i<=pnt[p][0]; i++)  
    42.         {  
    43.             t = pnt[p][i];  
    44.             //先释放,释放成功后再判断是否要加入队列  
    45.             if (dis[p]+map[p][t] < dis[t])  
    46.             {  
    47.                 dis[t] = dis[p]+map[p][t];  
    48.                 if (!vst[t])  
    49.                 {  
    50.                     Q[end++] = t;  
    51.                     vst[t] = 1;  
    52.                 }  
    53.             }  
    54.         }  
    55.         vst[p] = 0;  
    56.         pri++;  
    57.     }  
    58.     return 1;  
    59. }  

    1. 正规邻接表存储: 
    2. / ——- 邻接表存储 ———–
    3. struct Edge 
    4.     int e;  //终点 
    5.     int v;  //边权 
    6.     struct Edge nxt; 
    7. }; 
    8. struct 
    9.     struct Edge head, last; 
    10. } node[MAXN]; 
    11. / ——————————–
    12.  
    13. /  添加有向边<起点,终点,边权> 
    14. void add(int s,int e,int v) 
    15.     struct Edge p; 
    16.     p = (struct Edge)malloc(sizeof(struct Edge)); 
    17.     p->e = e; 
    18.     p->v = v; 
    19.     p->nxt = NULL; 
    20.     if (node[s].head == NULL) 
    21.     { 
    22.         node[s].head = p; 
    23.         node[s].last = p; 
    24.     } 
    25.     else 
    26.     { 
    27.         node[s].last->nxt = p; 
    28.         node[s].last = p; 
    29.     } 
    30.  
    31. /  松弛,成功返回1,否则0 
    32. int relax(int s,int e,int v) 
    33.     if (dis[s]+v < dis[e]) 
    34.     { 
    35.         dis[e] = dis[s]+v; 
    36.         return 1; 
    37.     } 
    38.     return 0; 
    39.  
    40. /  SPFA有负权回路返回0,否则返回1并且最短路径保存在dis[] 
    41. int n; 
    42. int vst[MAXN], cnt[MAXN]; 
    43. int Q[MAXNMAXN]; 
    44. int SPFA(int s0) 
    45.     int i, p, q; 
    46.     struct Edge *pp; 
    47.  
    48.     memset(vst, 0, sizeof(vst)); 
    49.     memset(cnt, 0, sizeof(cnt)); 
    50.     for (i=0; i<=n; i++) 
    51.         dis[i] = INF; 
    52.     dis[s0] = 0; 
    53.  
    54.     Q[0] = s0; p = 0; q = 1; 
    55.     vst[s0] = 1; 
    56.     cnt[s0]++; 
    57.     while (p < q) 
    58.     { 
    59.         pp = node[Q[p]].head; 
    60.         while (pp) 
    61.         { 
    62.             if (relax(Q[p], pp->e, pp->v) && !vst[pp->e]) 
    63.             { 
    64.                 Q[q++] = pp->e; 
    65.                 vst[pp->e] = 1; 
    66.                 cnt[pp->e]++; 
    67.                 if (cnt[pp->e] > n)
      //有负权回路 
    68.                     return 0; 
    69.             } 
    70.             pp = pp->nxt; 
    71.         } 
    72.         vst[Q[p]] = 0; 
    73.         p++; 
    74.     } 
    75.     return 1; 

      1. 正规邻接表存储:  
      2. / ——- 邻接表存储 ———– /  
      3. struct Edge  
      4. {  
      5.     int e;  //终点  
      6.     int v;  //边权  
      7.     struct Edge nxt;  
      8. };  
      9. struct  
      10. {  
      11.     struct Edge head, last;  
      12. } node[MAXN];  
      13. / ——————————– /  
      14.   
      15. /  添加有向边<起点,终点,边权>  /  
      16. void add(int s, int e, int v)  
      17. {  
      18.     struct Edge p;  
      19.     p = (struct Edge)malloc(sizeof(struct Edge));  
      20.     p->e = e;  
      21.     p->v = v;  
      22.     p->nxt = NULL;  
      23.     if (node[s].head == NULL)  
      24.     {  
      25.         node[s].head = p;  
      26.         node[s].last = p;  
      27.     }  
      28.     else  
      29.     {  
      30.         node[s].last->nxt = p;  
      31.         node[s].last = p;  
      32.     }  
      33. }  
      34.   
      35. /  松弛,成功返回1,否则0  /  
      36. int relax(int s, int e, int v)  
      37. {  
      38.     if (dis[s]+v < dis[e])  
      39.     {  
      40.         dis[e] = dis[s]+v;  
      41.         return 1;  
      42.     }  
      43.     return 0;  
      44. }  
      45.   
      46. /  SPFA有负权回路返回0,否则返回1并且最短路径保存在dis[]  /  
      47. int n;  
      48. int vst[MAXN], cnt[MAXN];  
      49. int Q[MAXNMAXN];  
      50. int SPFA(int s0)  
      51. {  
      52.     int i, p, q;  
      53.     struct Edge *pp;  
      54.   
      55.     memset(vst, 0, sizeof(vst));  
      56.     memset(cnt, 0, sizeof(cnt));  
      57.     for (i=0; i<=n; i++)  
      58.         dis[i] = INF;  
      59.     dis[s0] = 0;  
      60.   
      61.     Q[0] = s0; p = 0; q = 1;  
      62.     vst[s0] = 1;  
      63.     cnt[s0]++;  
      64.     while (p < q)  
      65.     {  
      66.         pp = node[Q[p]].head;  
      67.         while (pp)  
      68.         {  
      69.             if (relax(Q[p], pp->e, pp->v) && !vst[pp->e])  
      70.             {  
      71.                 Q[q++] = pp->e;  
      72.                 vst[pp->e] = 1;  
      73.                 cnt[pp->e]++;  
      74.                 if (cnt[pp->e] > n) //有负权回路  
      75.                     return 0;  
      76.             }  
      77.             pp = pp->nxt;  
      78.         }  
      79.         vst[Q[p]] = 0;  
      80.         p++;  
      81.     }  
      82.     return 1;  
      83. }  

      1. /通过poj 3159 证明:还是用数组来实现邻接表比用链表来实现邻接表效率高, 
      2.  
      3. #define MAX_node 10000 
      4. #define MAX_edge 100000 
      5.  
      6. struct Edge 
      7.     int e, v; 
      8. } edge[MAX_edge]; 
      9.  
      10. int neg;    //number of edge 
      11. int node[MAX_node];  //注意node要用memset初始化全部为-1 
      12. int next[MAX_edge]; 
      13.  
      14. void add(int s,int e,int v) 
      15.     edge[neg].e = e; 
      16.     edge[neg].v = v; 
      17.     next[neg] = node[s]; 
      18.     node[s] = neg++; 
      19. /  该题还证明用栈来实现SPFA比用队列来实现效率高,还节约空间
      20. int SPFA(int s0)//栈实现 
      21.     int i, t, p, top; 
      22.  
      23.     memset(vst, 0, sizeof(vst)); 
      24.     for (i=1; i<=n; i++) 
      25.         dis[i] = INF; 
      26.     dis[s0] = 0; 
      27.  
      28.     Q[0] = s0; 
      29.     top = 1; 
      30.     vst[s0] = 1; 
      31.     while (top) 
      32.     { 
      33.         t = Q[–top]; 
      34.         vst[t] = 0; 
      35.         p = node[t]; 
      36.         while (p != -1) 
      37.         { 
      38.             if (relax(t, edge[p].e, edge[p].v) && !vst[edge[p].e]) 
      39.             { 
      40.                 Q[top++] = edge[p].e; 
      41.                 vst[edge[p].e] = 1; 
      42.             } 
      43.             p = next[p]; 
      44.         } 
      45.     } 
      46.     return 1; 
      47. }


      48. 如果对我的博文有任何的意见或者建议,欢迎在文章的下方进行评论