SPFA

---恢复内容开始---

SPFA——O(k*E)
Shortest Path Faster Algorithm

•维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个起点S。用一个布尔数组记录每个点是否处在队列中。

• 每次迭代，取出队头的点v，依次枚举从v出发的边v→u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。

【程序】

 1 procedure spfa;
 2 begin
 3  fillchar(q,sizeof(q),0); 
 4  h:=0; t:=0;//队列
 5  fillchar(v,sizeof(v),false);//v[i]判断i是否在队列中
 6  for i:=1 to n do 
 7   dist[i]:=maxint;//初始化最小值
 8  inc(t); 
 9  q[t]:=1; 
10  v[1]:=true;
11  dist[1]:=0;//这里把1作为源点
12  while not(h=t) do
13  begin
14   h:=(h+1)mod n;
15   x:=q[h];  
16   v[x]:=false;//出队列
17   for i:=1 to n do
18    if (cost[x,i]>0)and(dist[x]+cost[x,i]<dist[i]) then
19     begin
20      dist[i]:=dist[x]+cost[x,i];
21      if not(v[i]) then
22        begin
23          t:=(t+1)mod n; 
24          q[t]:=i;
25          v[i]:=true
26        end;
27     end;
28  end;
29 end;

•SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身会再次被改进，于是再次用来改进其它的点，这样反复迭代下去。

---恢复内容结束---