SPFA演算法

① 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演算法一定可以找出最短路徑嗎

最開始隊列里只有一個起始點，在你處理你選的「第一個點」之前，必須要先處理完起始點，這時隊列里會有所有跟起始點相連的節點。然後按照你說的處理，第一點出列，然後不會有新的點加入，但是隊列里還有其他跟起始點相連的，所以一般不會為空，演算法繼續執行。如果隊列為空，則說明沒有點跟起始點相連了，那麼演算法也就可以終止了

③ 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

④ spfa演算法 無向圖中，一定要把檢查過的邊刪除，不然會重新檢查，形成死循環！

如果不做標記的話，訪問過的點雖然不能再更新其它值了，但是還會不停訪問下一個節點

⑤ Floyed演算法，spfa演算法，dij演算法各自的優勢都在哪裡哪個適用於無向圖哪個適用於負權邊急！

直覺感覺是迪傑斯特拉的比較好。。。留個名。

⑥ 來解釋下spfa和Dijkstra的優缺點

SPFA並不比Dijkstra慢多少
而且SPFA好寫 還能做負權、判負環
比賽的時候掌握Floyd和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;

⑨ 關於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始計數，你可以參考一下：