spfa课件讲义+前向星优化.doc

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

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

3、如果该式成立则将 dj 减小到 di+wi,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 数组里就保存了从源点到各

6、点的最短路径值 。下面举一个实例来说明 SFFA 算法是怎样进行的：设有一个有向图GV ，E，其中， VV0,V1,V2,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 算法执行的步骤及结果初始第一步第二步第三步第四步第五步queDqueDqueDqueDqueDque DueueueueueueV00V10V4

7、0V20V300V42V22222555599109999算法执行到第五步后，队Queue空，算法结束。源点V0 到 V1 的最短路径为 2，到 V2 的最短路径为 5，到 V3 的最短路径为 9，到 V4的最短路径为 9，结果显然是正确的。SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是 SPFA 中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。标准 SPFA 过程(以求某个结点t 到某个结点s 的最短路为例，稍加修改即为单源最短路 )Pas

8、cal语言代码constmaxp=10000;最大结点数 var 变量定义 p,c,s,t:longint;p, 结点数 ;c, 边数 ;s: 起点 ;t: 终点 a,b:array1.maxp,0.maxpof longint;ax,y 存 x,y 之间边的权 ;bx,c 存与 x 相连的第c 个边的另一个结点yd:array1.maxpofinteger;队列 v:array1.maxpofboolean;是否入队的标记dist:array1.maxpoflongint;到起点的最短路head,tail:longint;队首 / 队尾指针procedureinit;vari,x,y,z:l

9、ongint;beginread(p,c);for i := 1 to c dobeginreadln(x,y,z);x,y:一条边的两个结点;z: 这条边的权值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;procedurespfa(s:longint);SPFAvar i,j,now,sum:longint;beginfillchar(d,sizeof(d),0);fillchar(v,sizeof(v),f

10、alse);for j := 1 to p do distj:=maxlongint;dists:=0;vs:=true;d1:=s;队列的初始状态,s 为起点 head:=1;tail:=1;whilehead<=taildo队列不空beginnow:=dhead;取队首元素 for i:=1to bnow,0doif distbnow,i>distnow+anow,bnow,ibeginthendistbnow,i:=distnow+anow,bnow,i;修改最短路if notvbnow,ithen扩展结点入队begininc(tail);dtail:= bnow,i;vbn

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

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。此时该网络图可以用前向星形表示法

13、表示如下：节点对应的出弧的起始地址编号数组（记为point ）节点号 i123456起始地址 point (i )134679记录弧信息的数组弧编号12345678起点11234455终点23423534权89640367在数组point 中，其元素个数比图的节点数多1（即 n 1 ），且一定有point (1)1，point (n1)m1 。对于节点i ，其对应的出弧存放在弧信息数组的位置区间为 point (i ), point (i1)1 ，如果point (i )point (i1) ，则节点i 没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上相当于有序存放的“弧

14、表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（point ）记录每个节点出发的弧的起始编号。for i:=1 to m doreadln(ai,bi,ei);qsort(1,m);for i:=1 to m doif fai=0 then fai:=i;fn+1:=m+1;for i:=n downto 1 doif fi=0 then fi:=fi+1;通常用在点的数目太多， 或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。前向星最常用的是来优化spfa最基本的前项性优化的spfa( 有向图 )

15、vara,b,e:array1.1000oflongint;vis:array1.2000of boolean;q,d,f:array1.2001of longint;n,m,i,s,t:longint;procedureqsort(l,r:longint);var i,j,x,y:longint;begini:=l;j:=r;x:=a(l+r)shr1;repeatwhileai<xdo inc(i);whileaj>xdo dec(j);if not(i>j)thenbeginy:=ai;ai:=aj;aj:=y;y:=bi;bi:=bj;bj:=y;y:=ei;ei:=

16、ej;ej:=y;inc(i);dec(j);end;untili>j;if i<rthenqsort(i,r);if l<jthenqsort(l,j);end;procedurespfa(s:longint);var i,k,l,t:longint;beginfillchar(vis,sizeof(vis),0);for i:=1to n do di:=maxlongint;ds:=0;l:=0;t:=1;q1:=s;viss:=true;repeatl:=lmod10000+1;k:=ql;for i:=fkto fk+1-1doif dk+ei<dbithenb

17、egindbi:=dk+ei;if notvisbithenbegint:=tmod10000+1;qt:=bi;visbi:=true;end;end;visk:=false;untill=t;end;Beginreadln(n,m);for i:=1to m doreadln(ai,bi,ei);qsort(1,m);fori:=1tomdoif fai=0thenfai:=i;fn+1:=m+1;fori:=ndownto1 doif fi=0thenfi:=fi+1;readln(s,t);spfa(s);writeln(dt);end.例题 1 ：SweetButter香甜的黄油描述

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

19、AT :(file butter.in)第一行 : 三个数：奶牛数 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)一行 输出奶牛必须行走的最小的距离和SAMPLEINPUT3 4 52341 2 11 3 52 3 72 4 33 4 5program butter;varf1,f

20、2:text;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;ans:longint;procedure init;vari,j,x,y,z:longint;beginassign(f1,'butter.in');reset(f1);assign(f2,'butter.out');

21、rewrite(f2);readln(f1,N,P,C);fillchar(count,sizeof(count),0);for i:=1 to n do beginread(f1,x);inc(countx);end;for i:=1 to p dofor j:=1 to p doai,j:=maxlongint;for i:=1 to c do beginread(f1,x,y,z);inc(bx,0);bx,bx,0:=y;ax,y:=z;inc(by,0);by,by,0:=x;ay,x:=z;end;end;procedure spfa(s:longint);vari,j,now,s

22、um:longint;beginfillchar(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;while head<=tail do beginnow:=dhead;for i:=1 to bnow,0doifdistbnow,i>distnow+anow,bnow,i then begindistbnow,i:=distnow+anow,bnow,i;if not vbnow,i thenb

23、egininc(tail);dtail:=bnow,i;vbnow,i:=true;end;end;vnow:=false;inc(head);end;sum:=0;for i:=1 to p doif counti<>0 theninc(sum,counti*disti);if ans>sum then ans:=sum;end;procedure main;vari:longint;beginans:=maxlongint;for i:=1 to p do spfa(i);end;begininit;main;writeln(f2,ans);close(f2);end.赠

24、送以下学习资料和倍差倍问题学习目标通过和倍、差倍问题的学习，除了掌握这类问题的解决方法以外，其重点要学习画线段图。二、基础知识1. 和倍问题是已知两个数的和及它们之间的倍数关系而求这两个数各是多少的应用题。基本的数量关系： 和÷ ( 倍数 +1)=较小数 ( 即 1 倍数、标准数 )2. 差倍问题是已知两个数的差及它们之间的倍数关系而求这两个数各是多少的应用题。基本公式： 差÷ ( 倍数的差 ) 标准数 ( 一倍数 )例题解析一、和倍问题例 1：某班为“希望工程”捐款，两组少先队员共交废报纸 240 千克，第一组交的废报纸是第二组的 3 倍，问两组各交废报纸多少千克？小结：

25、解答基本的和倍问题，先确定其中一个数作为标准数 (1 倍数 ) ，再找出两数的和，及其相对应的倍数关系， 这样就可以求出标准数， 也就可求出另一个数(较大数)。基本的数量关系： 和÷ ( 倍数 +1)=较小数 ( 即 1 倍数、标准数 )练一练： NBA球星姚明到底有多高？现在已知小明和姚明的身高和是 339 厘米，姚明的身高大约是小明身高的 2 倍。你能够算出来吗？例 2：哥哥原有 108 元，弟弟有 60 元，如果现在想把哥哥的钱调整到弟弟的 5 倍，弟弟应给哥哥多少钱？练一练：妹妹有课外书 20 本，姐姐有课外书 25 本，姐姐给妹妹多少本后，妹妹课外书是姐姐的 2 倍？例 3

26、：二个同学共做了 23 道题。如果乙同学再多做 1 题，将是甲同学做的 2 倍，二个同学各做了几题？例 4：熊猫水果店运来水果 380 千克，其中苹果比梨的 3 倍还少 40 千克，水果店运来苹果和梨各多少千克 ?练一练： 果园里种桃树和梨树共 340 棵 , 其中桃树的棵数比梨树的 3 倍多 20 棵，梨树种了多少棵？例 5：三捆电线共长 273 米，其中第二根的长度是第一根长度的 2 倍，第三根的长度是第二根长度的 2 倍。三根电线各多少米？练一练： 甲、乙、丙三数的和是78，甲数比乙数的2 倍多 4，乙数比丙数的3倍少 2。求这三个数。例 6：某小学有学生 975 人 . 全校男生人数是六年级学生人数的 4 倍少 23 人，全校女生人数是六年级学生人数的 3 倍多 11 人. 问全校有男、女生各多少人？二、差倍问题例 1：某小学参观科普展览，第一天参观的人数比第二天多 200 人。已知第一天参观的人数是第二天的 3 倍，两天参观的各是多少人？练一练：已知甲、乙两个数的商是 4，而这两个数的差是 30，那么这两个数中较小的一个是多少？例 2：甲、乙两车间原来人数相等，因工作需要，从甲车间调24 人到乙车间. 这时乙车间人数是甲车间的4 倍. 甲、乙两个车间原