资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 图,图的基本概念,图的存储结构,图的遍历,最小生成树,最短路径,最短路径(Shortest Path),最短路径问题：,如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。,问题解法,单源最短路径 ,Dijkstra,算法,任意顶点对之间的最短路径,Floyd,算法,单源最短路径问题,问题的提出：,给定一个带权有向图,G,与源点,v,，求从,v,到,G,中其它顶点的最短路径。,限定各边上的权值大于或等于0。,为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。,举例说明,迪杰斯特拉(,Dijkstra,),算法思想,按路径长度递增次序产生最短路径算法：,把V,分成两组：,（1）S：已求出最短路径的顶点的集合,（2）V-S=T：尚未确定最短路径的顶点集合,将T中顶点按最短路径递增的次序加入到S中，,求最短路径步骤,初使时令,S=V0,T=,其余顶点，,T,中顶点对应的距离值,若存在，,为,弧上的权值,若不存在，,为,从,T,中选取一个其距离值为最小的顶点,W，,加入,S,对,T,中顶点的距离值进行修改：若加进,W,作中间顶点，从,V0,到,Vi,的距离值比不加,W,的路径要短，则修改此距离值,重复上述步骤，直到,S,中包含所有顶点，即,S=V,为止,Dijkstra逐步求解的过程,void,dijkstra,(Graph G,int v0,int dist,int path),int n=G.ver.size;,int*s=(int*)malloc(sizeof(int)*n);,int mindis,i,j,u;,for(i=0;in;i+),disti=G.edgev0i;,si=0;,if(i!=v0,else pathi=-1;,sv0=1;,for(i=1;in;i+),mindis=maxw;,for(j=0;j=n;j+),if(sj=0&distjmindis),u=j;,算法说明,对于顶点i和j：,1、首先，考虑从i到j是否有以顶点1为中间点的路径，：i，1，j，即考虑图中是否有边和，若有，则新路径i，1，j的长度是Ci1+C1j，比较路径i，j和i，1，j，的长度，并以较短者为当前所求得的最短路径，。该路径是中间点序号不大于1的最短路径。,所有顶点对之间的最短路径,2、其次，考虑从i到j是否包含顶点2为中间点的路径：i，.，2，.，j，若没有，则从i到j的最短路径仍然是第一步中求出的，即从i到j的中间点序号不大于1的最短路径；若有，则i，.，2，.，j可分解成两条路径i，.，2和2，.，j，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径相加就得到路径i，.，2，.，j的长度，将该长度与前一次求出的从i到j的中间点序号不大于1的最短路径长度比较，取其较短者作为当前求得的从i到j的中间点序号不大于2的最短路径。,算法的基本思想就是：,从初始的邻接矩阵A,0,开始，递推地生成矩阵序列A,1,，A,2,，.，A,n,显然，A中记录了所有顶点对之间的最短路径长度。若要求得到最短路径本身，还必须设置一个路径矩阵Pnn，在第k次迭代中求得的pathij，是从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。算法结束时，由pathij的值就可以得到从i到j的最短路径上的各个顶点。,50,10,30,10,20,60,100,C,1,高等数学,C,2,程序设计基础,C,3,离散数学 C,1,C,2,C,4,数据结构 C,3,C,2,C,5,高级语言程序设计 C,2,C,6,编译方法 C,5,C,4,C,7,操作系统 C,4,C,9,C,8,普通物理 C,1,C,9,计算机原理 C,8,课程代号,课程名称,先修课程,学生课程学习工程图,可以用,有向图,表示一个工程。在这种有向,图中，,用顶点表示活动,，,用有向边,表示活动的前后次序,。,V,i,必须先于活动,V,j,进行。这种有向图叫做顶点表示活动的,AOV,网络(,Activity On Vertices)。,在,AOV,网络中，如果活动,V,i,必须在活动,V,j,之前进行，则存在有向边，AOV,网络中不能出现有向回路，即有向环。在,AOV,网络中如果出现了有向环，则意味着,某项活动应以自己作为先决条件。,因此，对给定的,AOV,网络，必须先判断它,是否存在有向环。,检测有向环的一种方法是对,AOV,网络构造它的拓,扑有序序列。即将各个顶点(代表各个活动)排列,成一个线性有序的序列，使得,AOV,网络中所有应,存在的前驱和后继关系都能得到满足。,这种构造,AOV,网络全部顶点的拓扑有序序列的运,算就叫做拓扑排序。,如果通过拓扑排序能将,AOV,网络的所有顶点都排,入一个拓扑有序的序列中，则该,AOV,网络中必定,不会出现有向环；相反，如果得不到满足要求的,拓扑有序序列，则说明,AOV,网络中存在有向环，,此,AOV,网络所代表的工程是不可行的。,例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为,C,1,C,2,C,3,C,4,C,5,C,6,C,8,C,9,C,7,或,C,1,C,8,C,9,C,2,C,5,C,3,C,4,C,7,C,6,a,b,c,d,e,f,为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同时设置一个栈来存储所有入度为0 的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为0 的顶点都推入栈中，一旦排序过程中出现新的入度为0 的顶点，也同样将其推入栈中。,v1,0,v2,2,null,v3,1,v4,2,v5,3,null,v6,0,。,。,。,。,1,2,3,4,5,6,出边表,1、扫描顶点表，将入度为0 的顶点入栈；,2、while (栈非空),将栈顶顶点v弹出并输出之；,检查v的出边，将每条出边终点u的入度减1，,若u的入度变为0，则把u推入栈；,3、若输出的顶点数小于n，则输出“有回路”；否则拓扑,排序正常结束。,拓扑排序算法框架,0,2,1,2,3,0,0,2,1,2,3,1,0,2,1,1,2,1,0,1,4,0,2,1,top,top,top,top=0,1,2,3,4,5,6,0,4,4,0,1,1,0,4,4,0,1,1,0,4,4,0,0,1,0,4,4,0,0,1,top,top,top,1,2,3,4,5,6,TOPOSORT(vexnode dig),int i,j,k,m=0,top=-1;,edgenode*p;,for(i=0;iadjvex;,digk.id-;,if(digk.id=0),digk.id=top;,top=k;,p=p-next;,if(mn),printf(“nThe network,has a cyclen”);,算法分析,设AOV网有n个顶点，e条边。初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)，所以总的时间复杂度为O(n+e)。,关键路径,如果在,无有向环的带权有向图,中,用有向边表示一个工程中的各项活动(,Activity),用边上的权值表示活动的持续时间(,Duration),用顶点表示事件(,Event),AOE,网络在某些工程估算方面非常有用。例如，可以使人们了解：,(1)完成整个工程至少需要多少时间(假设网络中没有环).,(2)为缩短完成工程所需的时间,应当加快哪些活动.,则这样的有向图叫做用边表示活动的网络，简称,AOE,(Activity On Edges),网络。,在,AOE,网络中,有些活动,顺序进行,，有些活动,并,行进行,。,从源点到各个顶点，以至从源点到汇点的有向路,径可能不止一条。这些路径的长度也可能不同。,完成不同路径的活动所需的时间虽然不同，但只,有各条路径上所有活动都完成了，整个工程才算,完成。,因此，,完成整个工程所需的时间取决于从源点到,汇点的最长路径长度,，即在这条路径上所有活动,的持续时间之和。,这条路径长度最长的路径就叫,做关键路径,(,Critical Path)。,定义几个与计算关键活动有关的量：,事件,V,i,的最早可能开始时间,Ve,(,i,),是从,源点,V,0,到,顶点,V,i,的最长路径长度。,事件,V,i,的最迟允许开始时间,Vl,i,是在保证,汇点,V,n,-1,在,Ve,n,-1,时刻完成的前提,下，事件,V,i,的允许的最迟开始时间。,活动,a,k,的最早可能开始时间,e,k,设,活动,a,k,在,边,上，则,e,k,是从源点,V,0,到顶点,V,i,的最长路径长度。因此,e,k,=,Ve,i,。,活动,a,k,的最迟允许开始时间,l,k,l,k,是在不会引起时间延误的前提下，该活动允,许的最迟开始时间。,l,k,=,Vl,j,-,dur,()。,其中，,dur,()是完成,a,k,所需的时间。,时间余量,l,k,-,e,k,表示活动,a,k,的最早可能开始时间和最迟允许开始时间的时间余量。,l,k,=e,k,表示活动,a,k,是没有时间余量的,关键活动,。显然，关键路径上的所有活动都是关键活动。,为找出关键活动,需要求各个活动的,e,k,与,l,k,，,以判别是否,l,k,=e,k,.,为求得,e,k,与,l,k,，,需要先求得从源点,V,0,到各个顶点,V,i,的,Ve,i,和,Vl,i,。,求,Ve,i,的递推公式,从,Ve,0=0开始，向前递推,S2,i,=1,2,n,-1,其中,S,2是所有从,V,i,指向顶点,V,j,的有向边的集合。,从,Vl,n,-1=,Ve,n,-1开始，反向递推,S,1,i,=,n,-2,n,-3,0,其中,S,1是所有从顶点,V,i,发出的有向边的集合。,这两个递推公式的计算必须分别在拓扑有序及逆拓扑有,序的前提下进行。,设活动,a,k,(,k,=1,2,e,),在带权有向边,上,它的,持续时间用,dur,(),表示，则有,e,k,=,Ve,i,；,l,k,=,Vl,j,-,dur,()；,k,=1,2,e,。,这样就得到计算关键路径的算法。,计算关键路径时，可以一边进行拓扑排序一边计算各顶,点的,Ve,i,，,并按拓扑有序的顺序对各顶点重新进行了编,号。算法在求,Ve,i,i,=0,1,n,-1,时按拓扑有序的顺序计,算，在求,Vl,i,i,=,n,-1,n,-2,0,时按逆拓扑有序的顺序计,算。,v5,v1,v2,v3,v4,v6,v7,v8,v9,4,6,5,1,1,2,9,7,4,4,2,6,4,0,5,7,7,16,14,18,18,14,10,8,6,6,16,7,0,v5,v1,v2,v3,v4,v6,v7,v8,v9,4,6,5,1,1,2,9,7,4,4,2,6,4,0,5,7,7,16,14,18,18,14,10,8,6,6,16,7,0,活动,1-2,1-3,1-4,2-5,3-5,4-6,5-7,5-8,6-8,7-9,8-9,e,0,0,0,6,4,5,7,7,7,16,14,l,0,2,3,6,6,8,7,7,10,16,14,e-l,0,2,3,0,2,3,0,0,3,0,0,v5,v1,v2,v7,v8,v9,6,1,9,7,4,2,6,0,7,16,14,18,18,14,6,16,7,0,求关键路径的算法,typedef struct node1 /*,边表结点定义,*/,int adjvex;/*邻接点域*/,int dut;/*权值*/,struct node1*next;/*链域*/,edgenode1;,typedef struc
展开阅读全文