SPFA演算法
① SPFA演算法的pascal代碼
SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的時間復雜度內求出源點到其他所有點的最短路徑，可以處理負邊。SPFA的實現甚至比Dijkstra或者Bellman_Ford還要簡單：
設Dist[I]代表S到I點的當前最短距離，Fa[I]代表S到I的當前最短路徑中I點之前的一個點的編號。開始時Dist全部為+∞，只有Dist[S]=0，Fa全部為0。
維護一個隊列，裡面存放所有需要進行迭代的點。初始時隊列中只有一個點S。用一個布爾數組記錄每個點是否處在隊列中。
每次迭代，取出隊頭的點v，依次枚舉從v出發的邊v->u，設邊的長度為len，判斷Dist[v]+len是否小於Dist[u]，若小於則改進Dist[u]，將Fa[u]記為v，並且由於S到u的最短距離變小了，有可能u可以改進其它的點，所以若u不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空，也就是S到所有的最短距離都確定下來，結束演算法。
SPFA在形式上和寬度優先搜索非常類似，不同的是寬度優先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之後再次被放入隊列，也就是一個點改進過其它的點之後，過了一段時間可能本身被改進，於是再次用來改進其它的點，這樣反復迭代下去。設一個點用來作為迭代點對其它點進行改進的平均次數為k，有辦法證明對於通常的情況，k在2左右(怎麼證明的作者也不知道)。
const maxl=maxlongint;
var
g:array[1..100,1..100]of shortint;
b:array[1..1000]of boolean;
h,dis:array[1..1000]of longint;
x,s,e,i,j:longint;
procere inp;
begin
assign(input,'spfa.txt');reset(input);
readln(x,s,e);
for i:=1 to x do begin
for j:=1 to x do read(g[i,j]);
readln;
end;
for i:=1 to 1000 do dis[i]:=maxl;
fillchar(b,sizeof(b),false);
end;
procere spfa;
var
head,tail:longint;
procere relax(i:longint);
begin
if dis[i]>dis[h[head]]+g[h[head],i] then begin
if i=s then begin writeln('NO WAY');halt;end;{judge <0}
dis[i]:=dis[h[head]]+g[h[head],i];
if not b[i] then begin
inc(tail);
h[tail]:=i;
b[i]:=true;
end;
end;
end;
begin
head:=1;tail:=1;
h[1]:=s;
dis[s]:=0;
b[s]:=true;
repeat
for i:=1 to x do
if g[h[head],i]<>100 then relax(i);
b[h[head]]:=false;
inc(head);
until head>tail;
end;
begin
inp;
spfa;
writeln(dis[e]);
end.
② 用spfa演算法求最短路，如果圖中有負權環應如何處理
spfa 可以解決負權問題， 不用特殊處理
③ SPFA演算法可否取代Dijkstra演算法成為計算單源最短路徑的最優解
SPFA在稀疏圖上快，因為是通過邊來增廣的。dijkstra在稠密圖上快。因為是通過點來增廣的。某些情況下dijkstra 加上堆優化，在處理大數據的時候會比SPFA快很多；但是SPFA在隨機數據的綜合表現中相比dijkstra優勢還是比較大的。總而言之，各有所長。
④ SPFA演算法的偽代碼
SPFA實際上是Bellman-Ford基礎上的隊列優化
一種偽代碼 ProcereSPFA;Begininitialize-single-source(G,s);initialize-queue(Q);enqueue(Q,s);whilenotempty(Q)dobeginu:=dequeue(Q);foreachv∈adj[u]dobegintmp:=d[v];relax(u,v);if(tmp<>d[v])and(notvinQ)thenenqueue(Q,v);end;end;End;一種更容易讀懂的偽代碼: ProcereSPFA;Begininitialize-single-source(G,s);initialize-queue(Q);enqueue(Q,s);whilenotempty(Q)dobeginu:=dequeue(Q);foreachv∈adj[u]dobegintmp:=d[v];relax(u,v);if(tmp<>d[v])and(notvinQ)thenenqueue(Q,v);end;end;End;
⑤ 在使用spfa演算法一定可以找出最短路徑嗎
最開始隊列里只有一個起始點，在你處理你選的「第一個點」之前，必須要先處理完起始點，這時隊列里會有所有跟起始點相連的節點。然後按照你說的處理，第一點出列，然後不會有新的點加入，但是隊列里還有其他跟起始點相連的，所以一般不會為空，演算法繼續執行。如果隊列為空，則說明沒有點跟起始點相連了，那麼演算法也就可以終止了
⑥ dijkstra和spfa相比，那個更好一些
SPFA的時間復雜度其實是在胡扯。在Bellman-Ford的論文里提及了隊列優化，也就是現在的SPFA。k八成以上是瞎編的。原論文如下：
演算法編程後實際運算情況表明m一般沒有超過2n.事實上頂點入隊次數m是一個不容易事先分析出來的數,但它確是一個隨圖的不同而略有不同的常數.所謂常數,就是與e無關,與n也無關,僅與邊的權值分布有關.一旦圖確定,權值確定,原點確定,m就是一個確定的常數.所以SPFA演算法復雜度為O(e)
如果真的如這個所說，單源最短路徑的時間復雜度是O（1）。
其實spfa真正復雜度是O（n^2）
帶堆優化的dijkstra時間復雜度很低，為O(n logn)，比較一下就可以得出dijkstra更好，不會被卡。
然後呢……在NOI2018 DAY1T1的歸程中，spfa被萬惡（良心）的出題人卡了，這也意味著以後的比賽將會hack SPFA，所以退spfa入dijkstra+堆優化保平安
我是菜雞OIer chen_zhe
⑦ Floyed演算法，spfa演算法，dij演算法各自的優勢都在哪裡哪個適用於無向圖哪個適用於負權邊急！
直覺感覺是迪傑斯特拉的比較好。。。留個名。
⑧ 關於C++SPFA演算法求最短路徑的問題
用vs2017調試了一下，主要的問題就是初始化不完全，尤其是沒有對vis數組初始化。在調試的過程中，把數據的輸入改成文件形式了，不想弄成滑鼠手^_^
#include"pch.h"
#define_CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<iomanip>
#include<fstream>
usingnamespacestd;
constintSIZE=500;
intdis[SIZE]; //出發點到各點的最短估計距離
intpath[SIZE]; //路徑上到達該點的上一頂點
inta[SIZE][SIZE]; //a[i][j]表示i到j路徑的權值
//n為頂點數，s為出發點
//各頂點編號從1始起
voidspfa(intn,ints)
{
constintINF=999999; //初始最短路徑估計值
intvis[SIZE]; //該點是否被訪問過
intq[SIZE]; //用於實現spfa的隊列
for(inti=1;i<=n;i++)
{
path[i]=-1;
dis[i]=INF;
vis[i]=0;
}
dis[s]=0;vis[s]=1;q[1]=s;
intv,head=0,tail=1;
while(head<tail)
{
head++;
v=q[head];
vis[v]=0; //出隊
for(inti=1;i<=n;i++)
{
if(a[v][i]>0&&dis[i]>dis[v]+a[v][i])
{
dis[i]=dis[v]+a[v][i];
path[i]=v;
if(vis[i]==0)
{
tail++;
q[tail]=i;
vis[i]=1; //入隊
}
}
}
}
}
//k為終點
voidprintpath(intk)
{
if(path[k]!=-1)
printpath(path[k]);
cout<<"->"<<k;
}
intmain()
{
#defineWsetw(4)
ifstreamin("in.txt");
if(!in.is_open())
{
cout<<"未打開in.txt，請檢查文件是否在當前目錄下";
return0;
}
intn,s; //頂點數，出發點
in>>n>>s;
cout<<"輸入頂點數、出發點："<<n<<""<<s<<endl;
cout<<"輸入各條路徑的起點、終點、權值："<<endl;
inti=1;
while(in.peek()!=EOF) //in.eof()會多讀一行
{
intx,y,w;
in>>x>>y>>w;
a[x][y]=w;
//a[y][x]=w;
cout<<"第("<<W<<i++<<")條邊：";
cout<<W<<x<<W<<y<<W<<w<<endl;
}
cout<<endl;
spfa(n,s);
cout<<"從"<<s<<"到"<<n<<"的最短路徑:"<<dis[n]<<endl;
printpath(n);
return0;
}
in文件內容：
111
125
133
241
253
266
358
367
376
486
498
583
595
693
6103
798
7104
8113
9112
10112
網路裡面有個經典的c++ spfa程序，那個用了一點stl的知識，數組也從0始計數，你可以參考一下：
⑨ SPFA演算法的原理及證明
求單源最短路的SPFA演算法的全稱是：Shortest Path Faster Algorithm，是西南交通大學段凡丁於1994年發表的。從名字我們就可以看出，這種演算法在效率上一定有過人之處。很多時候，給定的圖存在負權邊，這時類似Dijkstra演算法等便沒有了用武之地，而Bellman-Ford演算法的復雜度又過高，SPFA演算法便派上用場了。簡潔起見，我們約定加權有向圖G不存在負權迴路，即最短路徑一定存在。如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）。當然，我們可以在執行該演算法前做一次拓撲排序，以判斷是否存在負權迴路，但這不是我們討論的重點。我們用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行鬆弛操作，直至隊列空為止。
定理：只要最短路徑存在，上述SPFA演算法必定能求出最小值。證明：每次將點放入隊尾，都是經過鬆弛操作達到的。換言之，每次的優化將會有某個點v的最短路徑估計值d[v]變小。所以演算法的執行會使d越來越小。由於我們假定圖中不存在負權迴路，所以每個結點都有最短路徑值。因此，演算法不會無限執行下去，隨著d值的逐漸變小，直到到達最短路徑值時，演算法結束，這時的最短路徑估計值就是對應結點的最短路徑值。
期望時間復雜度：O(me)， 其中m為所有頂點進隊的平均次數，可以證明m一般小於等於2：「演算法編程後實際運算情況表明m一般沒有超過2n.事實上頂點入隊次數m是一個不容易事先分析出來的數,但它確是一個隨圖的不同而略有不同的常數.所謂常數,就是與e無關,與n也無關,僅與邊的權值分布有關.一旦圖確定,權值確定,原點確定,m就是一個確定的常數.所以SPFA演算法復雜度為O(e).證畢.（SPFA的論文）不過，這個證明是非常不嚴謹甚至錯誤的，事實上在bellman演算法的論文中已有這方面的內容，所以國際上一般不承認SPFA演算法。
對SPFA的一個很直觀的理解就是由無權圖的BFS轉化而來。在無權圖中，BFS首先到達的頂點所經歷的路徑一定是最短路(也就是經過的最少頂點數)，所以此時利用數組記錄節點訪問可以使每個頂點只進隊一次，但在帶權圖中，最先到達的頂點所計算出來的路徑不一定是最短路。一個解決方法是放棄數組，此時所需時間自然就是指數級的，所以我們不能放棄數組，而是在處理一個已經在隊列中且當前所得的路徑比原來更好的頂點時，直接更新最優解。
SPFA演算法有兩個優化策略SLF和LLL——SLF：Small Label First 策略，設要加入的節點是j，隊首元素為i，若dist(j)<dist(i)，則將j插入隊首，否則插入隊尾； LLL：Large Label Last 策略，設隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)>x則將i插入到隊尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出隊進行鬆弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。 在實際的應用中SPFA的演算法時間效率不是很穩定，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra演算法。
⑩ 我編的SPFA演算法哪裡有錯誤
歐拉迴路
const maxn=100;
var
g:array[1..maxn,1..maxn] of longint;
:array[1..maxn] of longint;
circuit:array[1..maxn] of longint;
n,circuitpos,i,j,start,oddnumber:longint;
procere setIO;
begin
assign(input,'one.in');
reset(input);
assign(output,'one.out');
rewrite(output);
end;
procere find_circuit(i:longint);
var j:longint;
begin
for j:=1 to n do
if g[i,j]=1 then
begin
g[i,j]:=0;
g[j,i]:=0;
find_circuit(j);
end;
circuitpos:=circuitpos+1;
circuit[circuitpos]:=i;
end;
begin
// setIO;
read(n);
for i:=1 to n do
begin
[i]:=0;
for j:=1 to n do
begin
read(g[i,j]);
[i]:=[i]+g[i,j];
end;
end;
start:=1; oddnumber:=0;
for i:=1 to n do
if [i] mod 2 =1 then
begin
start:=i;
oddnumber:=oddnumber+1;
end;
if (oddnumber>2)or(oddnumber=1)
then writeln('No Solution!')
else begin
circuitpos:=0;
find_circuit(start);
for i:=1 to circuitpos-1 do write(circuit[i],'--->');
writeln(circuit[circuitpos]);
end;
close(input);close(output);
end.
SPFA
實現方法：建立一個隊列，初始時隊列里只有起始點，在建立一個表格記錄起始點到所有點的最短路徑（該表格的初始值要賦為極大值，該點到他本身的路徑賦為0）。然後執行鬆弛操作，用隊列里有的點去刷新起始點到所有點的最短路，如果刷新成功且被刷新點不在隊列中則把該點加入到隊列最後。重復執行直到隊列為空
判斷有無負環：如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）
program spfaprg;
const
maxp=10000;
var
p,c,s,t:longint;
a,b:array[1..maxp,0..maxp] of longint;
d:array[1..maxp] of integer;
v:array[1..maxp] of boolean;
dist:array[1..maxp] of longint;
head,tail:longint;
procere init;
var
i,x,y,z:longint;
begin
read(p,c);
for i := 1 to c do
begin
readln(x,y,z);
inc(b[x,0]); b[x,b[x,0]] := y; a[x,y] := z;
inc(b[y,0]); b[y,b[y,0]] := x; a[y,x] := z;
end;
readln(s,t);
end;
procere spfa(s:longint); ｛SPFA｝
var i,,j,now,sum:longint;
begin
fillchar(d,sizeof(d),0);
fillchar(v,sizeof(v),false);
for j := 1 to p do
dist[ j ]:=maxlongint;
dist[s] := 0; v[s] := true; d[1] := s;
head := 1; tail := 1;
while head<=tail do
begin
now := d[head];
for i := 1 to b[now,0] do
if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then
begin
dist[b[now,i]]:= dist[now]+a[now,b[now,i]];
if not v[b[now,i]] then
begin
inc(tail);
d[tail] := b[now,i];
v[b[now,i]] := true;
end;
end;
v[now] := false;
inc(head);
end;
end;
procere print;
begin
writeln(dist[t]);
end;
begin
init;
spfa(s);
print;
end.