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

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

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

實現(xiàn)方法：

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

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

首先建立起始點a到其余各點的
最短路徑表格

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

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

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

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

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

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

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

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

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

在最短路徑表中，e，g的最短路徑估值又變小，隊列中無e點，e入隊，隊列中存在g這個點，g不用入隊，此時隊列中元素為g，e

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

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

在最短路徑表中，g的最短路徑估值沒變化（松弛不成功），此時隊列中元素為b

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

在最短路徑表中，e的最短路徑估值沒變化（松弛不成功），此時隊列為空了

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

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