求最短路徑的算法有許多種，除了排序外，恐怕是OI界中解決同一類問題算法最多的了。最熟悉的無疑是Dijkstra，接著是Bellman-Ford，它們都可以求出由一個源點向其他各點的最短路徑；如果我們想要求出每一對頂點之間的最短路徑的話，還可以用Floyd-Warshall。

SPFA是這篇日志要寫的一種算法，它的性能非常好，代碼實現也并不復雜。特別是當圖的規模大，用鄰接矩陣存不下的時候，用SPFA則可以很方便地面對臨接表。每個人都寫過廣搜，SPFA的實現和廣搜非常相似。

如何求得最短路徑的長度值？

首先說明，SPFA是一種單源最短路徑算法，所以以下所說的“某點的最短路徑長度”，指的是“某點到源點的最短路徑長度”。

我們記源點為S，由源點到達點i的“當前最短路徑”為D[i]，開始時將所有D[i]初始化為無窮大，D[S]則初始化為0。算法所要做的，就是在運行過程中，不斷嘗試減小D[]數組的元素，最終將其中每一個元素減小到實際的最短路徑。

過程中，我們要維護一個隊列，開始時將源點置于隊首，然后反復進行這樣的操作，直到隊列為空：

(1)從隊首取出一個結點u，掃描所有由u結點可以一步到達的結點，具體的掃描過程，隨存儲方式的不同而不同；

(2)一旦發現有這樣一個結點，記為v，滿足D[v] > D[u] + w(u, v)，則將D[v]的值減小，減小到和D[u] + w(u, v)相等。其中，w(u, v)為圖中的邊u-v的長度，由于u-v必相鄰，所以這個長度一定已知（不然我們得到的也不叫一個完整的圖）；這種操作叫做松弛。

引用內容

松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在信息學中我們叫它三角不等式。所謂對i,j進行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果該式成立則將d[j]減小到d[i]+w[i,j]，否則不動。

(3)上一步中，我們認為我們“改進了”結點v的最短路徑，結點v的當前路徑長度D[v]相比于以前減小了一些，于是，與v相連的一些結點的路徑長度可能會相應地減小。注意，是可能，而不是一定。但即使如此，我們仍然要將v加入到隊列中等待處理，以保證這些結點的路徑值在算法結束時被降至最優。當然，如果連接至v的邊較多，算法運行中，結點v的路徑長度可能會多次被改進，如果我們因此而將v加入隊列多次，后續的工作無疑是冗余的。這樣，就需要我們維護一個bool數組Inqueue[]，來記錄每一個結點是否已經在隊列中。我們僅將尚未加入隊列的點加入隊列。


算法能否結束？

對于不存在負權回路的圖來說，上述算法是一定會結束的。因為算法在反復優化各個最短路徑長度，總有一個時刻會進入“無法再優化”的局面，此時一旦隊列讀空，算法就結束了。然而，如果圖中存在一條權值為負的回路，就糟糕了，算法會在其上反復運行，通過“繞圈”來無休止地試圖減小某些相關點的最短路徑值。假如我們不能保證圖中沒有負權回路，一種“結束條件”是必要的。這種結束條件是什么呢？

思考Bellman-Ford算法，它是如何結束的？顯然，最樸素的Bellman-Ford算法不管循環過程中發生了什么，一概要循環|V|-1遍才肯結束。憑直覺我們可以感到，SPFA算法“更聰明一些”，就是說我們可以猜測，假如在SPFA中，一個點進入隊列——或者說一個點被處理——超過了|V|次，那么就可以斷定圖中存在負權回路了。


最短路徑本身怎么輸出？

在一幅圖中，我們僅僅知道結點A到結點E的最短路徑長度是73，有時候意義不大。這附圖如果是地圖的模型的話，在算出最短路徑長度后，我們總要說明“怎么走”才算真正解決了問題。如何在計算過程中記錄下來最短路徑是怎么走的，并在最后將它輸出呢？

Path[]數組，Path[i]表示從S到i的最短路徑中，結點i之前的結點的編號。注意，是“之前”，不是“之后”。最短路徑算法的核心思想成為“松弛”，原理是三角形不等式，方法是上文已經提及的。我們只需要在借助結點u對結點v進行松弛的同時，標記下Path[v] = u，記錄的工作就完成了。

輸出時可能會遇到一點難處，我們記的是每個點“前面的”點是什么，輸出卻要從最前面往最后面輸，這不好辦。其實很好辦，見如下遞歸方法：

程序代碼

void PrintPath(int k){
    if( Path[k] ) PrintPath(Path[k]);
    fout<<k<<' ';
}

SPFA的代碼怎么寫？

我寫了鄰接表和鄰接矩陣兩種，兩者想像起來是那么的不同，算法的思路上實在區別不大，只是用不同方式詮釋“掃描”的過程而已。只給出SPFA的單個函數，我不覺得很容易看懂，但是我仍然把兩個程序的SPFA函數放在下面。在日志的結尾處，有一個完整版文件下載。貼程序，首先是鄰接表的：

程序代碼

void SPFA(){
    for(int i=1; i<=gv; i++)
        Dist[i] = 100000;
    Dist[S] = 0;
    int closed = 0, open = 1;
    queue[1] = S;
    Inqueue[S] = true;
    do{
        closed++;
        node *tmp = connect[queue[closed]];
        Inqueue[queue[closed]] = false;
        while(tmp != NULL){
            if( Dist[tmp->key] > Dist[queue[closed]] + tmp->w ){
                Dist[tmp->key] = Dist[queue[closed]] + tmp->w;
                Path[tmp->key] = queue[closed];
                if( !Inqueue[tmp->key] ){
                    Inqueue[tmp->key] = true;
                    open++;
                    queue[open] = tmp->key;
                }
            }
            tmp = tmp->next;
        }
    }while(closed < open);
}

然后是鄰接矩陣的：

程序代碼

void SPFA(){
    for( int i=1; i<=gv; i++){
        Dist[i] = 100000;
        for( int j=1; j<=gv; j++)
            if( !Graph[i][j] && i!=j) Graph[i][j] = 100000;
    }
    int closed = 0, open = 1;
    queue[1] = S;
    Dist[S] = 0;
    do{
        closed++;
        int u = queue[closed];
        Inqueue[u] = false;
        for(int i=1; i<=gv; i++)
            if ( Dist[i] > Dist[u] + Graph[u][i] ){
                Dist[i] = Dist[u] + Graph[u][i];
                Path[i] = u;
                if( !Inqueue[i] ){
                    Inqueue[i] = true;
                    open++;
                    queue[open] = i;
                }
            }
    }while(closed < open);
}

spfa算法 Easy sssp 收藏
輸入數據給出一個有N(2 <= N <= 1,000)個節點，M(M <= 100,000)條邊的帶權有向圖.
要求你寫一個程序, 判斷這個有向圖中是否存在負權回路. 如果從一個點沿著某條路徑出發, 又回到了自己, 而且所經過的邊上的權和小于0, 就說這條路是一個負權回路.
如果存在負權回路, 只輸出一行-1;
如果不存在負權回路, 再求出一個點S(1 <= S <= N)到每個點的最短路的長度. 約定: S到S的距離為0, 如果S與這個點不連通, 則輸出NoPath.

INPUT:
第一行: 點數N(2 <= N <= 1,000), 邊數M(M <= 100,000), 源點S(1 <= S <= N);
以下M行, 每行三個整數a, b, c表示點a, b(1 <= a, b <= N)之間連有一條邊, 權值為c(-1,000,000 <= c <= 1,000,000)

OUTPUT:
如果存在負權環, 只輸出一行-1, 否則按以下格式輸出
共N行, 第i行描述S點到點i的最短路:
如果S與i不連通, 輸出NoPath;
如果i = S, 輸出0;
其他情況輸出S到i的最短路的長度

INPUT:
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

OUTPUT:
0
6
4
-3
-2
7

注意：
題目說的不是很清楚，給出的圖不一定是完全聯通圖，有些是斷開的幾個圖，所以在判斷的源點是否有環以外還要分別對不同的點進行spfa呀。再進行分別的判斷和輸出。

有幾個優化：
1.可以先判斷是否有負權自環，有則直接輸出-1
2.在枚舉的過程中，當這個頂點的最短路(d[i])<0時，有負權回路，輸出-1.

【參考程序】：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long queue[1001],a[1001],psum[1001],dis[1001],l[1001][1001],cost[1001][1001];
long n,m,s,i,j;
bool hash[1001],bk;
void spfa(int s)
{
    int head,tail,start,now,i;
    for (i=1;i<=n;i++)
    {
        dis[i]=0xfffffff;
        psum[i]=0;
        hash[i]=false;
    }
    head=tail=1;hash[s]=true;
    psum[s]=1;dis[s]=0;queue[1]=s;
    while (head<=tail)
    {
        start=queue[(head-1)%n+1];
        hash[start]=true;
        for (i=1;i<=l[start][0];i++)
        {
            now=l[start][i];
            if (dis[now]>dis[start]+cost[start][now])
            {
                dis[now]=dis[start]+cost[start][now];
                if (!hash[now])
                {
                    hash[now]=true;
                    tail++;
                    queue[(tail-1)%n+1]=now;
                    psum[now]++;
                    if (psum[now]>n)
                    {//記錄每個點進隊的次數(判斷環的關鍵}
                        bk=false;
                        return;
                    }
                }
            }
        }
        head++;
        hash[start]=false;
        if (dis[s]<0)
        {//判斷環的一個優化
            bk=false;
            return;
        }
    }
}
void output()
{
    bk=true;
    spfa(s);
    if (!bk)
    {
        printf("-1\n");
        return;
    }
    memcpy(a,dis,sizeof(long)*(n+1));
    for (i=1;i<=n;i++)
      if (a[i]==0xfffffff)
      {
            bk=true;
            spfa(i);
            if (!bk)
            {
                printf("-1\n");
                return;
            }
      }
    for (i=1;i<=n;i++)
      if (a[i]==0xfffffff) printf("NoPath\n");
      else printf("%d\n",a[i]);
}
void input()
{
    scanf("%d%d%d",&n,&m,&s);
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        if (i==j) cost[i][j]=0;
        else cost[i][j]=0xfffffff;
    memset(l,0,sizeof(l));
    int x,y,c;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        if (c<cost[x][y])
        {
            cost[x][y]=c;
            l[x][0]++;
            l[x][l[x][0]]=y;
        }
    }
}
int main()
{
    input();
    output();
    system("pause");
    return 0;
}

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/bobcowwocb/archive/2009/09/14/4550188.aspx

SPFA算法模版+鄰接表實現

SPFA即shotest path faster algorithm，由意思就可以看出該算法效率比較高。

其實SPFA就是bellman-ford算法的一個優化。

具體做法是用一個隊列保存待松弛的點，然后對于每個出隊的點依次遍歷每個與他有邊相鄰的點（用鄰接表效率較高），如果該點可以松弛并且隊列中沒有該點則將它加入隊列中，如此迭代直到隊列為空。

據說平均效率是O（E），可見對邊稀疏的圖用此算法效果是相當可觀的。

 

若要判負環路,則記錄一個點的入隊次數,若超過邊數，則有負權環。

 

#include <iostream>
#include <queue>
using namespace std;

const long MAXN=10000;
const long lmax=0x7FFFFFFF;

typedef struct  
{
    long v;
    long next;
    long cost;
}Edge;


Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];

queue<long> q;

long m,n;//點,邊
void init()
{
    long i;
    long eid=0;

    memset(vist,0,sizeof(vist));
    memset(p,-1,sizeof(p));
    fill(Dis,Dis+MAXN,lmax);

    while (!q.empty())
    {
        q.pop();
    }

    for (i=0;i<n;++i)
    {
        long from,to,cost;
        scanf("%ld %ld %ld",&from,&to,&cost);

        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;

        //以下適用于無向圖
        swap(from,to);
        
        e[eid].next=p[from];
        e[eid].v=to;
        e[eid].cost=cost;
        p[from]=eid++;

    }
}

void print(long End)
{
    //若為lmax 則不可達
    printf("%ld\n",Dis[End]);    
}

void SPF()
{

    init();

    long Start,End;
    scanf("%ld %ld",&Start,&End);
    Dis[Start]=0;
    vist[Start]=true;
    q.push(Start);

    while (!q.empty())
    {
        long t=q.front();
        q.pop();
        vist[t]=false;
        long j;
        for (j=p[t];j!=-1;j=e[j].next)
        {
            long w=e[j].cost;
            if (w+Dis[t]<Dis[e[j].v])
            {
                Dis[e[j].v]=w+Dis[t];
                if (!vist[e[j].v])
                {
                    vist[e[j].v]=true;
                    q.push(e[j].v);
                }
            }
        }
    }

    print(End);

}

int main()
{
    while (scanf("%ld %ld",&m,&n)!=EOF)
    {
        SPF();
    }
    return 0;
}

0

0

0

(請您對文章做出評價)