登山者的仰望

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種隊列實現，減少了不必要的冗余計算。

算法大致流程是用一個隊列來進行維護。 初始時將源加入隊列。 每次從隊列中取出一個元素，并對所有與他相鄰的點進行松弛，若某個相鄰的點松弛成功，則將其入隊。 直到隊列為空時算法結束。

Code
Procedure SPFA;
 
Begin
   initialize-single-source(G,s);
   initialize-queue(Q);
   enqueue(Q,s);
   while not empty(Q) do begin
      u:=dequeue(Q);
      for each v∈adj[u] do begin
         tmp:=d[v];
         relax(u,v);
         if (tmp<>d[v]) and (not v in Q) then enqueue(v);
         end;
      end;
End;

Code
procedure spfa;
begin
fillchar(q,sizeof(q),0); h:=0; t:=0;//隊列
fillchar(v,sizeof(v),false);//v[i]判斷i是否在隊列中
for i:=1 to n do dist[i]:=maxint;//初始化最小值
 
inc(t); q[t]:=1; v[1]:=true;
dist[1]:=0;//這里把1作為源點
 
while not(h=t) do
begin
    h:=(h+1)mod n;x:=q[h];  v[x]:=false;
    for i:=1 to n do
     if (cost[x,i]>0)and(dist[x]+cost[x,i]<dist[i]) then
     begin
       dist[i]:=dist[x]+cost[x,i];
       if not(v[i]) then
       begin
         t:=(t+1)mod n; q[t]:=i;v[i]:=true;
       end;
     end;
end;
end;