夏令营集训日照一中提高2spfa算法

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算法必定能求出最小值。 证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路

3、径估计值就是对应结点的最短路径值。（证毕）期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。实现方法：建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）单源最短路径中的松弛操作对于图中的每个顶点vV，都设置一个属性dv，描述从源点s到v的最短路

4、径上权值的上界，称为最短路径估计。prev代表S到v的当前最短路径中v点之前的一个点的编号,我们用下面的过程来对最短路径估计和前趋进行初始化。（(V)时间）。经过初始化以后，对所有vV，prev=NULL，对vV-s，有ds=0以及dv=。实际松弛过程：在松弛一条边(u,v)的过程中，要测试是否可以通过u节点，对迄今找到的v的最短路径进行改进；如果可以改进的话，则更新dv和prev。一次松弛操作可以减小最短路径估计的值dv，并更新v的前趋域prev(S到v的当前最短路径中v点之前的一个点的编号)。下面的伪代码对边(u,v)进行一步松弛操作。融入实际的单源最短路径的算法中。RELAX(u, v,

5、 w) if(dvdu+w(u,v) dv=du+w(u,v); prev=u;松弛是改变最短路径和前趋的唯一方式。求右图a到g的最短路径首先建立起始点a到其余各点的最短路径表格abcdefgdi0首先源点a入队，当队列非空时：、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：abcdefgdi024815在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：abcdef

6、gdi02481530在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：abcdefgdi0248151511在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：abcdefgdi024815151119在最短路径表中，g的最短路径估值变小了，g在队列中不存在，

7、因此g要入队，此时队列中的元素为e，f，g队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：abcdefgdi024815151119在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：abcdefgdi024815131114在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e队首元素g点出队，对以g为起始点的所有边的终点依次

8、进行松弛操作（此处只有b点），此时路径表格状态为：abcdefgdi017815131114在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：abcdefgdi017815131114在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：abcdefgdi017815131114在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队

9、列为空了最终a到g的最短路径为最长路设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i j。设w（i，j）为边的长度，请设计算法，计算图G中间的最长路径。输入一个n，表示这个图中有n个顶点，后一个m，表示有m对路径，有向，算出此图中从1到n的最长路径。输入一个数n(2 = n = 1500)，表示有n个点，接下来一个数m = 50000，表示有m条路，接下来m行中每行输入2个数a ，b，v表示从a点到b点有条路，路的长度为v。输出从1到n之间的最长路.如果1,n之间没连通，输出1。2 11 2 1 2 01-1Pascal版#includeusing namesp

10、ace std;struct nodeint x; int value; int next;node e60000;int visited1505,dis1505,st1505,queue1000;int main() int n,m,u,v,w,start,h,r,cur; freopen(c.in,r,stdin); freopen(c.out,w,stdout); while(scanf(%d%d,&n,&m)!=EOF) for(int i=1;i=1500;i+) visitedi=0; disi=-1; sti=-1; for(int i=1;i=m;i+) scanf(%d%d%

11、dn,&u,&v,&w); ei.x=v; ei.value=w; ei.next=stu; stu=i; start=1; visitedstart=1; disstart=0; h=0; r=1; queuer=start; while(h!=r) h=(h+1)%1000; cur=queueh; int tmp=stcur; visitedcur=0; while(tmp!=-1) if (disetmp.xdiscur+etmp.value) disetmp.x=discur+etmp.value; if(visitedetmp.x=0) visitedetmp.x=1; r=(r+1)%1000; queuer=etmp.x; tmp=etmp.next; printf(%dn,disn); return 0; 最短路径的应用-差分约束系统如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如：xj-xi=bk(i,j1,n,k1,m),则称其为差分约束系统。差分约束系统是求解关于一组变量的特殊不等式组的方法。x1-x5-1x2-x51x3-x15x4-x14x4-x3-1x5-x3-3x5-x4-3 对于如下一组含个变量，个约束条件的不等式组：求解差分约束系统，可以转化成图论的单源最短路径问题。对于单源最短路径，设di表示源点到