关于SPFA算法.doc

关于SPFA算法

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左右。

【算法框架】
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; //点1入队并做标记
dist[1]:=0; //这里把1作为源点
while not(h=t) do begin
    x:=q[(h+1)mod n]; h:=(h+1)mod n; v[x]:=false;//出队
    for i:=1 to n do //枚举x指向的点i
    if (a[x,i]>0)and(dist[x]+a[x,i]<dist[i]) then
    begin
      dist[i]:=dist[x]+a[x,i]; //更新x指向点的最短路径长度
      if not(v[i]) then begin //如果i不在队列中，则将其放入队列，改进与之相关的点
         t:=(t+1)mod n; q[t]:=i; v[i]:=true;
      end;
    end;
end;
end;

例题 公园漫步(park.pas)

【问题描述】
小M 和小Z 饭后在公园散步，走着走着小Z 忽然想起来家中的水龙头没有关，于是他们要在最快的时间内走出公园赶到家中。为了简化问题的描述，我们把公园的景点用数字标号（从1 到N-1），在两个景点中之间会有道路连接，并且小M 和小Z 是好市民，他们不会穿越公园的草坪，只会沿着公园的小路行走。小Z想知道从他们当前所处的位置S 到公园的出口（标号为N）所需要的最短时间。
【输入格式】
输入文件的第一行3 个正整数，N、K、T 并且用空格隔开，分别表示公园景点数目、公园小路条数，以及他们当前所处的景点编号。
接下来K 行，每行三个整数，表示小路连接的两个景点的编号以及走过这条小路所需要的时间。
【输出格式】
一个整数，表示他们走出公园所需要的最短时间。

【输入样例】
3 2 1
1 2 3
2 3 4

【输出样例】
7

【数据规模和约定】
对于60%的数据，保证N<=1000，M<=10000。
对于100%的数据，保证N<=10000，M<=100000。
对于100%的数据，保证结果在231 内