SPFA算法

SPFA算法是西南交通大學段凡丁于1994年發表的。求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm。從名字我們就可以看出，這種算法在效率上一定有過人之處。

很多時候，給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的複雜度又過高，SPFA算法便派上用場了。有人稱spfa算法是最短路的萬能算法。本文中，我們規定有向權重圖G不存在負權回路，即最短路徑一定存在。

SPFA的算法（動态規劃思想）

變量：我們用數組dis 記錄每個結點的最短路徑值（在目前步驟時），可以用鄰接矩陣或鄰接表來存儲圖G。

設立一個先進先出的隊列q（C++的建議使用STL）用來儲存待處理的結點，将源點放入。每次處理隊列首元素u點，并且用u點目前的u點最短路徑值對離開u點所指向的結點v進行松弛操作（即從原點到u點然後到v點的路徑，判定是否dis[j]>dis[i]+map[i][j]，如果該式成立則将dis[j]減小到dis[i]+w[i][j]，否則不動），如果v點的最短路徑值有所調整，且v點不在目前的隊列中，就将v點放入隊尾。這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止。

下面舉一個執行個體來說明SPFA算法是怎樣進行的(還是dijkstra算法的例子）：

各點之間的距離如表所示。

map	i=1	2	3	4	5	6
j=1	120	INF	50	INF	INF
2	120	10	INF	INF	30
3	INF	10	30	INF	INF
4	50	INF	30	INF	50
5	INF	INF	INF	INF	300
6	INF	30	INF	50	300

i	1	2	3	4	5	6
dis[i]	INF	INF	INF	INF	INF

que

1

首先，取出隊首1點：

2點，0+120=120,120<INF，dis[2] = 120;

4點，0+50=50,50<INF,dis[4] = 50;

map	i=1	2	3	4	5	6
j=1	120	INF	50	INF	INF
2	120	10	INF	INF	30
3	INF	10	30	INF	INF
4	50	INF	30	INF	50
5	INF	INF	INF	INF	300
6	INF	30	INF	50	300

i	1	2	3	4	5	6
dis[i]	120	INF	50	INF	INF

que

2

4

然後2點:

i	1	2	3	4	5	6
dis[i]	120	130	50	INF	150

que

4

3

6

然後4點:

i	1	2	3	4	5	6
dis[i]	120	80	50	INF	100

que

3

6

然後3點:

map	i=1	2	3	4	5	6
j=1	120	INF	50	INF	INF
2	120	10	INF	INF	30
3	INF	10	30	INF	INF
4	50	INF	30	INF	50
5	INF	INF	INF	INF	300
6	INF	30	INF	50	300

i=	1	2	3	4	5	6
dis[i]	90	80	50	INF	100

que

6

2

然後6點:

i=	1	2	3	4	5	6
dis[i]	90	80	50	400	100

que

2

5

最後2點和5點，沒有變化：

i=	1	2	3	4	5	6
dis[i]	90	80	50	400	100

que

和廣搜bfs的差別

SPFA 在形式上和廣度(寬度)優先搜尋非常類似，不同的是bfs中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之後再次被放入隊列，也就是一個點改進過其它的點之後，過了一段時間可能本身被改進(重新入隊)，于是再次用來改進其它的點，這樣反複疊代下去。

算法的僞代碼

void spfa(s)//求單源點s到其它各頂點的最短距離

    for i=1 to ndo//初始化每點到s的距離，不在隊列

        dis[i]=∞;//∞為無限（程式中為INF）

       vis[i]=false;

    dis[s]=0;//将dis[源點]設為0

    vis[s]=true;//源點s入隊列

    head=0;

    tail=1;

    q[tail]=s;//源點s入隊, 頭尾指針賦初值

    whilehead<tail do

        head+1;//隊首出隊

       v=q[head];//隊首結點v

       vis[v]=false;//釋放對v的标記，可以重新入隊

        for 每條邊(v,i)//對于與隊首v相連的每一條邊

           if(dis[i]>dis[v]+a[v][i])//如果不滿足三角形性質

               dis[i]=dis[v]+a[v][i]//松弛dis[i]

           if(vis[i]=false)//不在隊列，則加入隊列

               tail+1;

               q[tail]=i;

               vis[i]=true;

最短路徑本身輸出

在一個圖中，我們僅僅知道結點A到結點E的最短距離，有時候意義不大。這個圖要求最短路徑的話，在算出最短路徑長度後，我們總要說明“怎麼走”才算真正解決了問題。

我們定義一個path數組，path[i]表示源點s到i的最短路程中，結點i之前的結點的編号(父結點)，我們在借助結點u對結點v松弛的同時，标記下path[v]=u，記錄的工作就完成了。

如何輸出呢？我們記錄的是每個點前面的點是什麼，輸出卻要從最前面到後面輸出，這很好辦，遞歸就可以了：

void printpath(int k){

    if(path[k]!=0)

        printpath(path[k]);

    printf("%d->",k);

}

int main(){

    //……

    printpath(path[x]);

    printf("%d\n",x);

    //……

}
           

spfa算法模闆(鄰接矩陣)：

#define INF 99999999

//準備：定義dis,a 初始化a

void spfa(int s/*s為起點*/){

    int i;

    //定義變量

    for(i = 0; i<= n; i ++)

        dis[i] =INF;

    dis[s] = 0;

    //初始化每點i到s的距離

    int q[n +1],head = 0,tail = 1;

    bool vis[n +1];

    vis[s] = 1;

    q[1] = s;

    //隊列初始化

        int v;

        while(head< tail){//隊列非空

               head++;

               v =q[head];//取隊首元素

               vis[v]= 0;//釋放隊首結點，因為這節點可能下次用來松弛其它節點，重新入隊

               for(i= 0; i <= n; i ++)//對所有頂點

           if(a[v][i] > 0 && dis[i] > dis[v] + a[v][i]){

               dis[i] = dis[v] + a[v][i];//修改最短路

                               if(vis[i]== 0){//如果擴充結點i不在隊列中，入隊

                                      tail++;

                                      q[tail]= i;

                                      vis[i]= 1;

                               }

            }

        }

}