小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

SPFA 算法詳解( 強(qiáng)大圖解，不會(huì)都難！)

 Rainboy913 2013-12-08

適用范圍：給定的圖存在負(fù)權(quán)邊，這時(shí)類(lèi)似Dijkstra等算法便沒(méi)有了用武之地，而B(niǎo)ellman-Ford算法的復(fù)雜度又過(guò)高，SPFA算法便派上用場(chǎng)了。 我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判?，以判斷是否存在?fù)權(quán)回路，但這不是我們討論的重點(diǎn)。

算法思想：我們用數(shù)組d記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，用鄰接表來(lái)存儲(chǔ)圖G。我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開(kāi)u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止

 

期望的時(shí)間復(fù)雜度O(ke)， 其中k為所有頂點(diǎn)進(jìn)隊(duì)的平均次數(shù)，可以證明k一般小于等于2。

 

實(shí)現(xiàn)方法：

　　建立一個(gè)隊(duì)列，初始時(shí)隊(duì)列里只有起始點(diǎn)，再建立一個(gè)表格記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值，該點(diǎn)到他本身的路徑賦為0）。然后執(zhí)行松弛操作，用隊(duì)列里有的點(diǎn)作為起始點(diǎn)去刷新到所有點(diǎn)的最短路，如果刷新成功且被刷新點(diǎn)不在隊(duì)列中則把該點(diǎn)加入到隊(duì)列最后。重復(fù)執(zhí)行直到隊(duì)列為空。

判斷有無(wú)負(fù)環(huán)：
　　如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)N次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）

 


 

 

 

首先建立起始點(diǎn)a到其余各點(diǎn)的
最短路徑表格

                                 

首先源點(diǎn)a入隊(duì)，當(dāng)隊(duì)列非空時(shí)：
　１、隊(duì)首元素（a）出隊(duì)，對(duì)以a為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有b,c,d三個(gè)點(diǎn)），此時(shí)路徑表格狀態(tài)為：

                                 

在松弛時(shí)三個(gè)點(diǎn)的最短路徑估值變小了，而這些點(diǎn)隊(duì)列中都沒(méi)有出現(xiàn)，這些點(diǎn)
需要入隊(duì)，此時(shí)，隊(duì)列中新入隊(duì)了三個(gè)結(jié)點(diǎn)b,c,d

隊(duì)首元素b點(diǎn)出隊(duì)，對(duì)以b為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有e點(diǎn)），此時(shí)路徑表格狀態(tài)為：

                                

在最短路徑表中，e的最短路徑估值也變小了，e在隊(duì)列中不存在，因此e也要
入隊(duì)，此時(shí)隊(duì)列中的元素為c，d，e

隊(duì)首元素c點(diǎn)出隊(duì)，對(duì)以c為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有e,f兩個(gè)點(diǎn)），此時(shí)路徑表格狀態(tài)為：

                                

在最短路徑表中，e，f的最短路徑估值變小了，e在隊(duì)列中存在，f不存在。因此
e不用入隊(duì)了，f要入隊(duì)，此時(shí)隊(duì)列中的元素為d，e，f

 隊(duì)首元素d點(diǎn)出隊(duì)，對(duì)以d為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有g(shù)這個(gè)點(diǎn)），此時(shí)路徑表格狀態(tài)為：

 

 

                              

在最短路徑表中，g的最短路徑估值沒(méi)有變?。ㄋ沙诓怀晒Γ?，沒(méi)有新結(jié)點(diǎn)入隊(duì)，隊(duì)列中元素為f，g

隊(duì)首元素f點(diǎn)出隊(duì)，對(duì)以f為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有d，e，g三個(gè)點(diǎn)），此時(shí)路徑表格狀態(tài)為：


                               

在最短路徑表中，e，g的最短路徑估值又變小，隊(duì)列中無(wú)e點(diǎn)，e入隊(duì)，隊(duì)列中存在g這個(gè)點(diǎn)，g不用入隊(duì)，此時(shí)隊(duì)列中元素為g，e

隊(duì)首元素g點(diǎn)出隊(duì)，對(duì)以g為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有b點(diǎn)），此時(shí)路徑表格狀態(tài)為：

                          

在最短路徑表中，b的最短路徑估值又變小，隊(duì)列中無(wú)b點(diǎn)，b入隊(duì)，此時(shí)隊(duì)列中元素為e，b
隊(duì)首元素e點(diǎn)出隊(duì)，對(duì)以e為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有g(shù)這個(gè)點(diǎn)），此時(shí)路徑表格狀態(tài)為：

 

                         

在最短路徑表中，g的最短路徑估值沒(méi)變化（松弛不成功），此時(shí)隊(duì)列中元素為b

隊(duì)首元素b點(diǎn)出隊(duì)，對(duì)以b為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有e這個(gè)點(diǎn)），此時(shí)路徑表格狀態(tài)為：

                        

在最短路徑表中，e的最短路徑估值沒(méi)變化（松弛不成功），此時(shí)隊(duì)列為空了

最終a到g的最短路徑為１４

 

 

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;  //這個(gè)初始化給下邊那個(gè)while循環(huán)帶來(lái)影響
      }
 
   for(int i=1;i<=m;i++)
      {
       scanf("%d%d%d\n",&u,&v,&w);    
       e[i].x=v;            //記錄后繼節(jié)點(diǎn)    相當(dāng)于鏈表中的創(chuàng)建一個(gè)節(jié)點(diǎn)，并使得數(shù)據(jù)域先記錄
       e[i].value=w;
       e[i].next=st[u];     //記錄頂點(diǎn)節(jié)點(diǎn)的某一個(gè)邊表節(jié)點(diǎn)的下標(biāo)，相當(dāng)于在鏈表中吧該邊表節(jié)點(diǎn)的next指針先指向他的后繼邊表節(jié)點(diǎn)
       st[u]=i;                //把該頂點(diǎn)的指針指向邊表節(jié)點(diǎn)，相當(dāng)于鏈表中的插入中，頭結(jié)點(diǎn)的指針改變
      }
    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)            //改成大于號(hào)才對(duì)
            {
                   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;  
}


 

                     (沒(méi)有質(zhì)量，就出數(shù)量)  下面一文轉(zhuǎn)載出處：http://blog.csdn.net/morgan_xww/article/details/6279596

  1. /*
  2. SPFA(Shortest Path Faster Algorithm) [圖的存儲(chǔ)方式為鄰接表]
  3. 是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。
  4. 算法大致流程是用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)。 初始時(shí)將源加入隊(duì)列。 每次從隊(duì)列中取出一個(gè)元素，
  5. 并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個(gè)相鄰的點(diǎn)松弛成功，則將其入隊(duì)。 直到隊(duì)列為空時(shí)算法結(jié)束。
  6. 它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。
  8. SPFA 在形式上和BFS非常類(lèi)似，不同的是BFS中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中
  9. 一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之后，過(guò)了一段時(shí)間可能本
  10. 身被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。
  12. 判斷有無(wú)負(fù)環(huán)：如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)V次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）。
  14. SPFA算法有兩個(gè)優(yōu)化算法 SLF 和 LLL：
  15. SLF：Small Label First 策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dist(j)<dist(i)，則將j插入隊(duì)首，
  16. 否則插入隊(duì)尾。
  17. LLL：Large Label Last 策略，設(shè)隊(duì)首元素為i，隊(duì)列中所有dist值的平均值為x，若dist(i)>x則將i插入
  18. 到隊(duì)尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出對(duì)進(jìn)行松弛操作。
  19. 引用網(wǎng)上資料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。
  20. 在實(shí)際的應(yīng)用中SPFA的算法時(shí)間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。
  21. */ 
  22.  
  23. //用數(shù)組實(shí)現(xiàn)鄰接表存儲(chǔ)，pnt[i,0]表示與i相鄰的結(jié)點(diǎn)個(gè)數(shù)，pnt[i,1...k]存儲(chǔ)與i相鄰的點(diǎn) 
  24. int  pnt[MAXN][MAXN]; 
  25. int  map[MAXN][MAXN]; //map[i,j]為初始輸入的i到j(luò)的距離，并且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.             //先釋放，釋放成功后再判斷是否要加入隊(duì)列 
  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. SPFA(Shortest Path Faster Algorithm) [圖的存儲(chǔ)方式為鄰接表] 
  3. 是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。 
  4. 算法大致流程是用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)。 初始時(shí)將源加入隊(duì)列。 每次從隊(duì)列中取出一個(gè)元素， 
  5. 并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個(gè)相鄰的點(diǎn)松弛成功，則將其入隊(duì)。 直到隊(duì)列為空時(shí)算法結(jié)束。 
  6. 它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。 
  7.  
  8. SPFA 在形式上和BFS非常類(lèi)似，不同的是BFS中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中 
  9. 一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之后，過(guò)了一段時(shí)間可能本 
  10. 身被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。 
  11.  
  12. 判斷有無(wú)負(fù)環(huán)：如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)V次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）。 
  13.  
  14. SPFA算法有兩個(gè)優(yōu)化算法 SLF 和 LLL： 
  15. SLF：Small Label First 策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dist(j)<dist(i)，則將j插入隊(duì)首， 
  16. 否則插入隊(duì)尾。 
  17. LLL：Large Label Last 策略，設(shè)隊(duì)首元素為i，隊(duì)列中所有dist值的平均值為x，若dist(i)>x則將i插入 
  18. 到隊(duì)尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出對(duì)進(jìn)行松弛操作。 
  19. 引用網(wǎng)上資料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。 
  20. 在實(shí)際的應(yīng)用中SPFA的算法時(shí)間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。 
  21. */  
  22.   
  23. //用數(shù)組實(shí)現(xiàn)鄰接表存儲(chǔ)，pnt[i,0]表示與i相鄰的結(jié)點(diǎn)個(gè)數(shù)，pnt[i,1...k]存儲(chǔ)與i相鄰的點(diǎn)  
  24. int  pnt[MAXN][MAXN];  
  25. int  map[MAXN][MAXN]; //map[i,j]為初始輸入的i到j(luò)的距離，并且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.             //先釋放，釋放成功后再判斷是否要加入隊(duì)列  
  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. 正規(guī)鄰接表存儲(chǔ)： 
  2. /* ------- 鄰接表存儲(chǔ) ----------- */ 
  3. struct Edge 
  4. { 
  5.     int e;  //終點(diǎn) 
  6.     int v;  //邊權(quán) 
  7.     struct Edge *nxt; 
  8. }; 
  9. struct 
  10. { 
  11.     struct Edge *head, *last; 
  12. } node[MAXN]; 
  13. /* -------------------------------- */ 
  14.  
  15. /*  添加有向邊<起點(diǎn),終點(diǎn),邊權(quán)>  */ 
  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有負(fù)權(quán)回路返回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) //有負(fù)權(quán)回路 
  75.                     return 0; 
  76.             } 
  77.             pp = pp->nxt; 
  78.         } 
  79.         vst[Q[p]] = 0; 
  80.         p++; 
  81.     } 
  82.     return 1; 
  83. } 
  1. 正規(guī)鄰接表存儲(chǔ)：  
  2. /* ------- 鄰接表存儲(chǔ) ----------- */  
  3. struct Edge  
  4. {  
  5.     int e;  //終點(diǎn)  
  6.     int v;  //邊權(quán)  
  7.     struct Edge *nxt;  
  8. };  
  9. struct  
  10. {  
  11.     struct Edge *head, *last;  
  12. } node[MAXN];  
  13. /* -------------------------------- */  
  14.   
  15. /*  添加有向邊<起點(diǎn),終點(diǎn),邊權(quán)>  */  
  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有負(fù)權(quán)回路返回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) //有負(fù)權(quán)回路  
  75.                     return 0;  
  76.             }  
  77.             pp = pp->nxt;  
  78.         }  
  79.         vst[Q[p]] = 0;  
  80.         p++;  
  81.     }  
  82.     return 1;  
  83. }  
  1. /**通過(guò)poj 3159 證明：還是用數(shù)組來(lái)實(shí)現(xiàn)鄰接表比用鏈表來(lái)實(shí)現(xiàn)鄰接表效率高，  **/ 
  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. /*  該題還證明用棧來(lái)實(shí)現(xiàn)SPFA比用隊(duì)列來(lái)實(shí)現(xiàn)效率高，還節(jié)約空間 */ 
  23. int SPFA(int s0)//棧實(shí)現(xiàn) 
  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. }

 

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶(hù)發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶(hù) 評(píng)論公約

    類(lèi)似文章 更多