SPFA算法

  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[MAXN*MAXN];  
  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. {  
  8.     int e, v;  
  9. } edge[MAX_edge];  
  10.   
  11. int neg;    //number of edge  
  12. int node[MAX_node];  //注意node要用memset初始化全部为-1  
  13. int next[MAX_edge];  
  14.   
  15. void add(int s, int e, int v)  
  16. {  
  17.     edge[neg].e = e;  
  18.     edge[neg].v = v;  
  19.     next[neg] = node[s];  
  20.     node[s] = neg++;  
  21. }  
  22. /*  该题还证明用栈来实现SPFA比用队列来实现效率高，还节约空间 */  
  23. int SPFA(int s0) //栈实现  
  24. {  
  25.     int i, t, p, top;  
  26.   
  27.     memset(vst, 0, sizeof(vst));  
  28.     for (i=1; i<=n; i++)  
  29.         dis[i] = INF;  
  30.     dis[s0] = 0;  
  31.   
  32.     Q[0] = s0;  
  33.     top = 1;  
  34.     vst[s0] = 1;  
  35.     while (top)  
  36.     {  
  37.         t = Q[--top];  
  38.         vst[t] = 0;  
  39.         p = node[t];  
  40.         while (p != -1)  
  41.         {  
  42.             if (relax(t, edge[p].e, edge[p].v) && !vst[edge[p].e])  
  43.             {  
  44.                 Q[top++] = edge[p].e;  
  45.                 vst[edge[p].e] = 1;  
  46.             }  
  47.             p = next[p];  
  48.         }  
  49.     }  
  50.     return 1;  
  51. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/amourjun/p/5134224.html