這個(gè)算法，簡(jiǎn)單的說就是隊(duì)列優(yōu)化的bellman-ford,利用了每個(gè)點(diǎn)不會(huì)更新次數(shù)太多的特點(diǎn)發(fā)明的此算法（僅為個(gè)人理解=.=）
SPFA——Shortest Path Faster
Algorithm，它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。SPFA的實(shí)現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡(jiǎn)單：
設(shè)Dist代表S到I點(diǎn)的當(dāng)前最短距離，F(xiàn)a代表S到I的當(dāng)前最短路徑中I點(diǎn)之前的一個(gè)點(diǎn)的編號(hào)。開始時(shí)Dist全部為+∞，只有Dist[S]=0，F(xiàn)a全部為0。
維護(hù)一個(gè)隊(duì)列，里面存放所有需要進(jìn)行迭代的點(diǎn)。初始時(shí)隊(duì)列中只有一個(gè)點(diǎn)S。用一個(gè)布爾數(shù)組記錄每個(gè)點(diǎn)是否處在隊(duì)列中。
每次迭代，取出隊(duì)頭的點(diǎn)v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長(zhǎng)度為len，判斷Dist[v]+len是否小于Dist，若小于則改進(jìn)Dist，將Fa記為v，并且由于S到u的最短距離變小了，有可能u可以改進(jìn)其它的點(diǎn)，所以若u不在隊(duì)列中，就將它放入隊(duì)尾。這樣一直迭代下去直到隊(duì)列變空，也就是S到所有的最短距離都確定下來，結(jié)束算法。
SPFA
在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時(shí)間可能本身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。設(shè)一個(gè)點(diǎn)用來作為迭代點(diǎn)對(duì)其它點(diǎn)進(jìn)行改進(jìn)的平均次數(shù)為k，有辦法證明對(duì)于通常的情況，k在2左右
前向星優(yōu)化：
不要把前向星想成什么高深莫測(cè)的東西……它其實(shí)就是一種鄰接表的緊縮存儲(chǔ)形式。
為什么叫前向星？因?yàn)樗菍⑦叞凑涨岸它c(diǎn)排序，并用一個(gè)數(shù)組k[i]記錄端點(diǎn)i第一次以左端點(diǎn)出現(xiàn)的位置。這樣，我們就能用O(E)的空間復(fù)雜度存儲(chǔ)下一個(gè)鄰接表，而避免了鏈表或N^2的龐大空間消耗。
當(dāng)然，實(shí)際上我們并不需要排序：因?yàn)槲覀冎恍枰滥骋粭l邊應(yīng)該放到什么位置即可。因而我們還需要一個(gè)數(shù)組t[i]存儲(chǔ)從i出發(fā)的邊的條數(shù)。則需要存儲(chǔ)在的位置就可以很輕易地求得。（詳見代碼）
Butter題目代碼如下：
Program butter(input,output);
Type
edge=record
x,y,d:longint;
end;
Var
min,res,n,p,c,x,y,i,j,l,r:longint;
te,e:array[0..3000] of edge;
tk,t,k,num,d:array[1..800] of longint;
q:array[1..100000] of longint;
use:array[1..800] of boolean;
Procedure swap(var n1,n2:longint);
Var
tmp:longint;
Begin
tmp:=n1;n1:=n2;n2:=tmp;
End;
Begin
assign(input,'butter.in');reset(input);
readln(n,p,c);
for i:=1 to n do
begin
read(x);
|
