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;

procedure 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;

procedure spfa;

var

head,tail:longint;

procedure 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;

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.