《链式向前星和spfa算法》由会员分享，可在线阅读，更多相关《链式向前星和spfa算法（24页珍藏版）》请在金锄头文库上搜索。
1、2014暑假集训 acm519,一、图的储存 二、SPFA算法 三、树上最长路,1.1.图的数组(邻接矩阵)存储表示 邻接矩阵是用于描述图中顶点之间关系(即弧或边的权)的矩阵。 假设图中顶点数为n，则邻接矩阵Ann： 1 若Vi和Vj之间有边 Aij= 0 反之,注意： 1) 图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。 2) 无向图的邻接矩阵必然是对称矩阵。 3) 无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。,网的邻接矩阵, 反之,权值 若Vi和V
2、j之间有弧或边,Aij=,图的数组（邻接矩阵）存储表示 #define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enum DG, DN, UDG, UDN GraphKind; /图类型（有向图/网,无向图/网） typedef struct ArcCell VRType adj; /VRType是顶点关系类型。对无权图，用1或0 表示相邻否； 对带权图，则为权值类型。 InfoType *info; / 指向该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_V
3、ERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; / 描述顶点的数组 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;,1.2 链式前向星 向前星： （1）.把边的起点终点和权值存起来，然后以起点从小到大（或者从大到小）排序， （2）记录每个顶点在数组中的起始位置和长度。 链式前向星： 采用数组模拟链表实现前向星的功能 （1）为什么要学？ 他可以完美取代邻接表，不用去动态分配结点空间。 （2）链式前
4、向星构造方法如下： 每读入一条边 i 的信息 将边的终点和权值存放在 edgei中 把该条边的 next=headlista， headlista=i。 这样，前向星就构造完了.,例如：,#include #include using namespace std; #define maxedge 20000 #define maxn 5000 /结点数 struct Edge int t; /边的终点 int next;/当前下一条边的编号 int w; /边的权值 edgemaxedge; int headlistmaxedge; /索引 headi存放已 i 为起点的“第一条”边 int
5、n,m; void show_graph() /输出前向星存储的图 int i,k; for(i=1;i %d)=%dn“, i, edgek.t, edgek.w); ,int main() Int i,a,b,c; while(scanf(“%d%d“, ,SPFA算法,求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 最短路径快速算法SPFA算法是西南交通大学段凡丁于1994年发表的。,适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。,算
6、法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。,SPFA算法实现,SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用
7、来改进其它的点，这样反复迭代下去。,定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。 证明： 每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）,期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。,Relax(u,v) If （F(v)F(u)+W_Cost(u,v)） F(
8、v)=F(u)+W_Cost (u,v); ,SPFA的核心正是松弛操作：,求右图a到g的最短路径,首先建立起始点a到其余各点的 最短路径表格,首先源点a入队，当队列非空时： 、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：,在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点 需要入队，此时，队列中新入队了三个结点b,c,d,队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：,在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要 入队，此时队列
9、中的元素为c，d，e,队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：,在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此 e不用入队了，f要入队，此时队列中的元素为d，e，f,队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：,在最短路径表中，g的最短路径估值变小了，g在队列中不存在，因此g要入队，此时队列中的元素为e，f，g,队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：,在最短路径表中，g的最短路
10、径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g,队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：,在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e,队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：,在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b,队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：,在最短
11、路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b,队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：,在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了,最终a到g的最短路径为,#include #define MAX 999999 using namespace std; struct node int x; int value; int next; ; node e60000; int visited1505,dis1505,headlist1505,queue1000; int main() int
12、 n,m,u,v,w,start,h,r,cur; while(scanf(“%d%d“, ,for(int i=1;i=m;i+) scanf(“%d%d%dn“,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; ,树上最长路 现有结论： 从任意一点u出发搜到
13、的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路,证明： 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中已经证明过了 所以现在又有两种情况了： 1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t) 2：u走到最远点的路径u-T与s-t无交点，则dis(u，T) dis(u,X)+dis(X,t);显然，如果这个式子成立， 则dis(u,T)+dis(s,X)+dis(u,X)dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾,
