算法簡介
求單源最短路的SPFA算法的全稱是：ShortestPathFasterAlgorithm。
SPFA算法是西南交通大學段凡丁於1994年發表的.
從名字我們就可以看出，這種算法在效率上一定有過人之處。
很多時候，給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的複雜度又過高，SPFA算法便派上用場了。
簡潔起見，我們約定有向加權圖G不存在負權迴路，即最短路徑一定存在。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權迴路，但這不是我們討論的重點。
我們用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的佇列用來保存待最佳化的結點，最佳化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的佇列中，就將v點放入隊尾。這樣不斷從佇列中取出結點來進行鬆弛操作，直至佇列空為止。
定理:只要最短路徑存在，上述SPFA算法必定能求出最小值。
證明：每次將點放入隊尾，都是經過鬆弛操作達到的。換言之，每次的最佳化將會有某個點v的最短路徑估計值d[v]變小。所以算法的執行會使d越來越小。由於我們假定圖中不存在負權迴路，所以每個結點都有最短路徑值。因此，算法不會無限執行下去，隨著d值的逐漸變小，直到到達最短路徑值時，算法結束，這時的最短路徑估計值就是對應結點的最短路徑值。（證畢）
期望的時間複雜度O(ke)，其中k為所有頂點進隊的平均次數，可以證明k一般小於等於2。
實現方法：建立一個佇列，初始時佇列里只有起始點，在建立一個表格記錄起始點到所有點的最短路徑（該表格的初始值要賦為極大值，該點到他本身的路徑賦為0）。然後執行鬆弛操作，用佇列里有的點去刷新起始點到所有點的最短路，如果刷新成功且被刷新點不在佇列中則把該點加入到佇列最後。重複執行直到佇列為空。判斷有無負環：如果某個點進入佇列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）
對spfa的一個很直觀的理解就是由無權圖的bfs轉化而來.在無權圖中,bfs首先到達的頂點所經歷的路徑一定是最短路(也就是經過的最少頂點數).所以此時利用visit[u],可以使每個頂點只進隊一次.在帶權圖中,最先到達的頂點所計算出來的路徑不一定是最短路.一個解決方法是放棄visit數組,此時所需時間自然就是指數級的.所以我們不能放棄visit數組,而是在處理一個已經在佇列中且當前所得的路徑比原來更好的頂點時,直接更新最優解.
偽代碼
1.INITIALIZE-SINGLE-SOURCE(G,s)
2.INITIALIZE-QUEUE(Q)
3.ENQUEUE(Q,s)
4.WhileNotEMPTY(Q)
5.Dou<-DLQUEUE(Q)
6.For每條邊(u,v)inE[G]
7.Dotmp<-d[v]
8.Relax(u,v,w)
9.If(d[v]<tmp)and(v不在Q中)
10.ENQUEUE(Q,v)
程式實現（PASCAL 鍊表）
programspfa;{ByZine.Chant}typelink=^node;
node=record
x,y:longint;{x是指向的節點，y是邊權}
next:link;
end;
vari,n,m,x,y,z,start,head,tail:longint;
f:array[1..10000]oflongint;{當前最優值}
a:array[1..10000]oflink;{每個點連出的邊的鍊表的頭}
d:array[1..1000000]oflongint;{佇列}
o:array[1..10000]ofboolean;{檢驗元素是否在未被處理的佇列中}
r:link;
proceduresetup;
begin
assign(input,'spfa.in');
assign(output,'spfa.out');
reset(input);
rewrite(output);
end;
procedureendit;
begin
close(input);
close(output);
end;
begin
setup;
readln(n,m);{點和邊的個數}
readln(start);{起點}
fori:=1tondo
begin
new(a[i]);
fillchar(a[i]^,sizeof(a[i]^),0);{要有初始化的好習慣}
end;
fori:=1tomdo
begin
readln(x,y,z);
new(r);
r^.x:=y;
r^.y:=z;
r^.next:=a[x]^.next;
a[x]^.next:=r;
new(r);
r^.x:=x;
r^.y:=z;
r^.next:=a[y]^.next;
a[y]^.next:=r;
end;{讀入邊}
head:=0;
tail:=1;
d[1]:=start;
fori:=1tondo
f[i]:=maxlongint;
f[start]:=0;
fillchar(o,sizeof(o),false);
whilehead<taildo
begin
inc(head);
o[d[head]]:=false;{這三處是spfa的核心最佳化}
r:=a[d[head]];
whiler^.next<>nildo
begin
r:=r^.next;
iff[d[head]]+r^.y<f[r^.x]then
begin
f[r^.x]:=f[d[head]]+r^.y;
ifo[r^.x]thencontinue;{這三處是spfa的核心最佳化}
inc(tail);
d[tail]:=r^.x;
o[d[tail]]:=true;{這三處是spfa的核心最佳化}
end;
end;
end;
fori:=1tondo
writeln(i:5,':',f[i]:8);{輸出起點到每一個點的最短路徑}
endit;
end.
