链式向前星和SPFA算法ppt课件

2014暑假集训acm519,一、图的储存二、SPFA算法三、树上最长路,1,1.1.图的数组(邻接矩阵)存储表示邻接矩阵是用于描述图中顶点之间关系(即弧或边的权)的矩阵。假设图中顶点数为n，则邻接矩阵Ann：1若Vi和Vj之间有边Aij=0反之,2,3,注意：1)图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。2)无向图的邻接矩阵必然是对称矩阵。3)无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。,4,网的邻接矩阵,反之,权值若Vi和Vj之间有弧或边,Aij=,5,图的数组（邻接矩阵）存储表示#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/最大顶点个数typedefenumDG,DN,UDG,UDNGraphKind;/图类型（有向图/网,无向图/网）typedefstructArcCellVRTypeadj;/VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;/指向该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/描述顶点的数组AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧(边)数GraphKindkind;/图的种类标志MGraph;,6,1.2链式前向星向前星：（1）.把边的起点终点和权值存起来，然后以起点从小到大（或者从大到小）排序，（2）记录每个顶点在数组中的起始位置和长度。链式前向星：采用数组模拟链表实现前向星的功能（1）为什么要学？他可以完美取代邻接表，不用去动态分配结点空间。（2）链式前向星构造方法如下：每读入一条边i的信息将边的终点和权值存放在edgei中把该条边的next=headlista，headlista=i。这样，前向星就构造完了.,7,例如：,8,#include#includeusingnamespacestd;#definemaxedge20000#definemaxn5000/结点数structEdgeintt;/边的终点intnext;/当前下一条边的编号intw;/边的权值edgemaxedge;intheadlistmaxedge;/索引headi存放已i为起点的“第一条”边intn,m;voidshow_graph()/输出前向星存储的图inti,k;for(i=1;i%d)=%dn,i,edgek.t,edgek.w);,9,intmain()Inti,a,b,c;while(scanf(%d%d,10,SPFA算法,求单源最短路的SPFA算法的全称是：ShortestPathFasterAlgorithm。最短路径快速算法SPFA算法是西南交通大学段凡丁于1994年发表的。,适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。,算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。,11,SPFA算法实现,SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。,12,定理:只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）,期望的时间复杂度O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。,13,Relax(u,v)If（F(v)F(u)+W_Cost(u,v)）F(v)=F(u)+W_Cost(u,v);,SPFA的核心正是松弛操作：,14,求右图a到g的最短路径,首先建立起始点a到其余各点的最短路径表格,首先源点a入队，当队列非空时：、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：,在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d,15,队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：,在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e,队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：,在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f,16,队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：,在最短路径表中，g的最短路径估值变小了，g在队列中不存在，因此g要入队，此时队列中的元素为e，f，g,队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：,在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g,17,队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：,在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e,队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：,在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b,18,队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：,在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b,队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：,在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了,最终a到g的最短路径为,19,#include#defineMAX999999usingnamespacestd;structnodeintx;intvalue;intnext;nodee60000;intvisited1505,dis1505,headlist1505,queue1000;intmain()intn,m,u,v,w,start,h,r,cur;while(scanf(%d%d,20,for(inti=1;idiscur+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);return0;,22,树上最长路现有结论：从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路,23,证明：1设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则dis(u,T)dis(u,s)且dis(u,T)dis(u,t)则最长路不是s-t了，与假设矛盾2设u不为s-t路径上的点首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了所以现在又有两种情况