設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.