讲义+前向星优化

1、SPFA算法求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的. 从名字我们就可以看出，这种算法在效率上一定有过人之处。 很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。 我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。

2、我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。 证明：每次将点放入队尾，都是经过松弛操作达到的。（松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对i,j进行松弛，就是判定是否dj>di+wi,j，如果该式成立则将dj减小到di+wi,

3、j，否则不动。）换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕） 期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。 实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，

4、如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空 判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图） 在一幅图中，我们仅仅知道结点A到结点E的最短路径长度是73，有时候意义不大。这附图如果是地图的模型的话，在算出最短路径长度后，我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的，并在最后将它输出呢？Path数组，Pathi表示从S到i的最短路径中，结点i之前的结点的编号。注意，是“之前”，不是“之后”。最短路径算法的核心思想成为“松弛”，原理是三角形不等式，方法是上文已经提及的。我们只需要在借助结

5、点u对结点v进行松弛的同时，标记下Pathv = u，记录的工作就完成了。 SPFA算法采用图的存储结构是邻接表，方法是动态优化逼近法。算法中设立了一个先进先出的队列Queue用来保存待优化的顶点，优化时从此队列里顺序取出一个点w，并且用w点的当前路径DW去优化调整其它各点的路径值Dj，若有调整，即Dj的值改小了，就将J点放入Queue队列以待继续进一步优化。反复从Queue队列里取出点来对当前最短路径进行优化，直至队空不需要再优化为止，此时D数组里就保存了从源点到各点的最短路径值 。 下面举一个实例来说明SFFA算法是怎样进行的： 设有一个有向图GV，E，其中，VV0,V1,V2,

6、V3,V4，E<V0,V1>,<V0,V4>,<V1,V2>,<V1,V4>,<V2,V3>,<V3,V4>,<V4,V2>2,10,3,7,4,5,6，见下图： 算法执行时各步的Queue队的值和D数组的值由下表所示。表一 实例图SPFA算法执行的步骤及结果初始第一步第二步第三步第四步第五步queueDqueueDqueueDqueueDqueueDqueueDV00V10V40V20V300V42V22222555599109999算法执行到第五步后，队Queue空，算法结束。源点V0到V1的最短路径为2，

7、到V2的最短路径为5，到V3的最短路径为9，到V4的最短路径为9，结果显然是正确的。SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。标准SPFA过程(以求某个结点t到某个结点s的最短路为例，稍加修改即为单源最短路) Pascal语言代码const maxp=10000; 最大结点数 var 变量定义 p,c,s,t:longint; p,结点数;c,边数;s:起点;t:终点 a,b:arr

8、ay1.maxp,0.maxp of longint; ax,y存x,y之间边的权;bx,c存与x相连的第c个边的另一个结点y d:array1.maxp of integer; 队列 v:array1.maxp of boolean; 是否入队的标记 dist:array1.maxp of longint; 到起点的最短路 head,tail:longint; 队首/队尾指针 procedure init; var i,x,y,z:longint; begin read(p,c); for i := 1 to c do begin readln(x,y,z); x,y:一条边的两个结点;z:

9、这条边的权值 inc(bx,0); bx,bx,0 := y; ax,y := z; bx,0：以x为一个结点的边的条数 inc(by,0); by,by,0 := x; ay,x := z; end; readln(s,t); 读入起点与终点 end; procedure spfa(s:longint); SPFA var i,j,now,sum:longint; begin fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false); for j := 1 to p do distj:=maxlongint; dists:=0; vs:=tru

10、e;d1:=s;队列的初始状态,s为起点 head:=1;tail:= 1; while head<=tail do 队列不空 begin now:=dhead; 取队首元素 for i:=1 to bnow,0 do if distbnow,i>distnow+anow,bnow,i then begin distbnow,i:= distnow+anow,bnow,i; 修改最短路 if not vbnow,i then 扩展结点入队 begin inc(tail); dtail := bnow,i; vbnow,i := true; end; end; vnow := fal

11、se; 释放结点，一定要释放掉，因为这节点有可能下次用来松弛其它节点inc(head); 出队 end; end; procedure print; begin writeln(distt); end; begin init; spfa(s); print; end. 前向星优化星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点出发的所有孤。对每条弧，要依次存放其起点、终点、权的数

12、值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下： 节点对应的出弧的起始地址编号数组（记为）节点号123456

13、起始地址134679记录弧信息的数组弧编号12345678起点11234455终点23423534权89640367在数组中，其元素个数比图的节点数多1（即），且一定有，。对于节点，其对应的出弧存放在弧信息数组的位置区间为，如果，则节点没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（）记录每个节点出发的弧的起始编号。for i:=1 to m do readln(ai,bi,ei); qsort(1,m); for i:=1 to m do if fai=0 then fai:=i; f

14、n+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; 通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。 前向星最常用的是来优化spfa最基本的前项性优化的spfa(有向图)var a,b,e:array1.1000 of longint; vis:array1.2000 of boolean; q,d,f:array1.2001 of longint; n,m,i,s,t:longint; procedure qsort(l,r:longin

15、t); var i,j,x,y:longint; begin i:=l; j:=r; x:=a(l+r) shr 1; repeat while ai<x do inc(i); while aj>x do dec(j); if not(i>j) then begin y:=ai; ai:=aj; aj:=y; y:=bi; bi:=bj; bj:=y; y:=ei; ei:=ej; ej:=y; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); en

16、d; procedure spfa(s:longint); var i,k,l,t:longint; begin fillchar(vis,sizeof(vis),0); for i:=1 to n do di:=maxlongint; ds:=0; l:=0; t:=1; q1:=s; viss:=true; repeat l:=l mod 10000 +1; k:=ql; for i:=fk to fk+1-1 do if dk+ei<dbi then begin dbi:=dk+ei; if not visbi then begin t:=t mod 10000 +1; qt:=b

17、i; visbi:=true; end; end; visk:=false; until l=t; end; Begin readln(n,m); for i:=1 to m do readln(ai,bi,ei); qsort(1,m); for i:=1 to m do if fai=0 then fai:=i; fn+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; readln(s,t); spfa(s); writeln(dt); end. 例题1：Sweet Butter 香甜的黄油 描述 农夫John发现做出全威斯康辛州最甜的

18、黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。 农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那） 格式 PROGRAM NAME : butter INPUT FORMAT : (file butter.in)

19、第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450) 第二行到第N+1行: 1到N头奶牛所在的牧场号 第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的 OUTPUT FORMAT : (file butter.out) 一行 输出奶牛必须行走的最小的距离和 SAMPLE INPUT 3 4 52341 2 11 3 52 3 72 4 33 4 5program butter;var    f1,f2:text;&

20、#160;   n,p,c:longint;     count:array1.800of longint;    a,b:array1.800,0.800of longint;     d:array1.20000 of integer;    v:array1.800 of boolean;    dist:array1.800 of longint;    head,tail:longint

21、;    ans:longint;procedure init;    var      i,j,x,y,z:longint;     begin      assign(f1,'butter.in');reset(f1);      assign(f2,'butter.out');rewrite(f2);  

22、60;    readln(f1,N,P,C);      fillchar(count,sizeof(count),0);       for i:=1 to n do begin        read(f1,x);        inc(countx);      

23、;                                             end;      

24、;                                              for i:=1 to p do   

25、;     for j:=1 to p do          ai,j:=maxlongint;            for i:=1 to c do begin         read(f1,x,y,z);        

26、                                        inc(bx,0);bx,bx,0:=y;ax,y:=z;       

27、0;         inc(by,0);by,by,0:=x;ay,x:=z;            end;       end; procedure spfa(s:longint);    var      i,j,now,sum:longint;    

28、0;  begin      fillchar(d,sizeof(d),0);      fillchar(v,sizeof(v),false);      for i:=1 to p do disti:=maxlongint;      dists:=0;vs:=true;d1:=s;      head:=1;tail:=1;

29、60;     while head<=tail do begin        now:=dhead;        for i:=1 to bnow,0 do                        &#

30、160;         if distbnow,i>distnow+anow,bnow,i then begin          distbnow,i:=distnow+anow,bnow,i;                   if not vbnow,i then

31、 begin                                 inc(tail);                     

32、               dtail:=bnow,i;           vbnow,i:=true;                                end;