第17讲-图的应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/21,第七章 图,执行上课礼，不迟到、不早退、不旷课,课上不吃早点、不玩手机、不睡觉,第,17,讲 图的应用,主讲人：陈红丽,执行上课礼,1,主要内容,图的应用,关键路径,最短路径,知识点回顾,图的应用,最小生成树,拓扑排序,执行上课礼，不迟到、不早退、不旷课,2,课上不吃早点、不玩手机、不睡觉,对工程，人们至少关心如下两类问题：,工程能否顺利进行，即工程流程是否“合理”,通常用,AOV,网表示工程流程，进行拓扑排序,完成整项工程必须的最短时间，哪些子工程是影响工程进度的关键子工程,为计算完成整个工程至少需要多少时间，需将每一子工程所需的时间作为权值赋给图的各边，通常用,AOE,网表示工程,AOE,网,(Activity On Edge net),在一个表示工程的带权有向图中，用,顶点表示事件,，用,有向边表示活动,，边上的,权值表示活动的持续时间,，称这样的有向图叫做,边表示活动,的网（,AOE,）。,V,3,V,1,V,4,V,6,V,5,V,2,a,4,=3,a,1,=3,a,2,=2,a,6,=3,a,5,=4,a,3,=2,a,7,=2,a,8,=1,顶点表示事件,弧表示活动,源点：,开始事件,(,入度为,0),汇点：,结束事件,(,出度为,0),执行上课礼，不迟到、不早退、不旷课,3,课上不吃早点、不玩手机、不睡觉,AOE,网的性质：,只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；,只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。,V,3,V,1,V,4,V,6,V,5,V,2,a,4,=3,a,1,=3,a,2,=2,a,6,=3,a,5,=4,a,3,=2,a,7,=2,a,8,=1,事件 事件含义,v,1,v,2,v,3,v,6,开工,活动,a,1,完成，活动,a,3,、,a,4,可以开始,活动,a,2,完成，活动,a,5,和,a,6,可以开始,活动,a,6,、,a,7,和,a,8,完成，整个工程完成,事件,V,j,发生,表示,a,k,已结束,a,k,V,j,V,i,事件,V,i,发生,表示,a,k,可以开始,执行上课礼，不迟到、不早退、不旷课,4,课上不吃早点、不玩手机、不睡觉,路径长度,：,路径上各活动持续时间之和,。,关键路径,：,在,AOE,网中，从始点到终点路径长度最大的路径,。,关键路径长度是完成工程的最短工期,。,要找出关键路径，必须找出,关键活动,即不按期完成就会影响整个工程完成的活动。,关键活动：,关键路径上的活动。,V,3,V,1,V,4,V,6,V,5,V,2,a,4,=3,a,1,=3,a,2,=2,a,6,=3,a,5,=4,a,3,=2,a,7,=2,a,8,=1,回答下列问题：,1.,完成整个工程,至少,需要多少时间,?,2.,为缩短完成工程所需的时间，应当加快哪些活动,?,取决于从始点到终点的,最长路径长度,执行上课礼，不迟到、不早退、不旷课,5,课上不吃早点、不玩手机、不睡觉,首先计算以下与关键活动有关的量：,事件的最早发生时间,vei,事件的最迟发生时间,vli,活动的最早开始时间,ek,活动的最晚开始时间,lk,活动是,关键活动,的充要条件：,l(k,)=,e(k,),a,k,v,j,v,i,设活动,a,k,用弧,表示,a,k,持续时间为,:,dut,(),vei,是指从始点开始到顶点,v,i,的最大路径长度。这个长度决定了所有从顶点,v,i,发出的活动能够开工的最早时间。,ve1=0,vej,=,maxvei+dut,()(,pj,),pj,表示所有到达,v,j,的有向边的集合,事件的最早发生时间,vei,Vei,计算次序,：,为保证,V,i,所有前驱事件的最早发生时间已经求出，必须按,拓扑序列,的次序，依次计算,活动是,关键活动,的充要条件：,V,3,V,1,V,4,V,6,V,5,V,2,a,4,=3,a,1,=3,a,2,=2,a,6,=3,a,5,=4,a,3,=2,a,7,=2,a,8,=1,ve1=ve2=,ve5=ve3=,ve4=ve6=,0,3,6,2,6,8,v,i,v,j,执行上课礼，不迟到、不早退、不旷课,6,课上不吃早点、不玩手机、不睡觉,vli,是指在不推迟整个工期的前提下，事件,v,i,允许的最晚发生时间。,事件的最迟发生时间,vli,v,j,v,i,vln,=,ven,vli,=,minvlj-dut,(),（,si,）,si,为所有从,v,i,发出的有向边的集合,计算次序,：,为保证,V,i,所有后继事件的最迟发生时间已经求出，必须按,逆拓扑序列,的次序，依次计算,Vlj,V,3,V,1,V,4,V,6,V,5,V,2,a,4,=3,a,1,=3,a,2,=2,a,6,=3,a,5,=4,a,3,=2,a,7,=2,a,8,=1,ve1=0 ve2=3 ve5=6 ve3=2 ve4=6 ve6=8,vl1=vl2=vl5=vl3=vl4=vl6=,8,6,2,7,4,0,执行上课礼，不迟到、不早退、不旷课,7,课上不吃早点、不玩手机、不睡觉,活动的最早开始时间,ek,若活动,a,k,是由弧,表示，则活动,a,k,的最早开始时间应等于弧尾事件,v,i,的最早发生时间。因此，有：,ek,=,vei,活动,a,k,的最晚开始时间是指，在不推迟整个工期的前提下，,a,k,必须开始的最晚时间。要保证弧头事件,v,j,的最迟发生时间不拖后。因此，有：,lk,=,vlj-dut,(),活动的最晚开始时间,lk,a,k,v,j,v,i,执行上课礼，不迟到、不早退、不旷课,8,课上不吃早点、不玩手机、不睡觉,求解下图的关键路径（写出详细过程）,V,4,V,2,V,1,V,6,V,5,V,3,V,7,V,8,V,9,a,1,=6,a,2,=4,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=9,a,8,=7,a,9,=4,a,10,=2,a,11,=4,执行上课礼，不迟到、不早退、不旷课,9,课上不吃早点、不玩手机、不睡觉,求关键路径步骤,求,Ve(i,),求,Vl(i,),求,e(k,),求,l(k,),事件,最早发生时间,(,Ve,),最晚发生时间,(,Vl,),V,1,0,0,V,2,3,4,V,6,2,2,V,8,6,6,V,4,6,7,V,9,8,8,V,3,6,6,V,7,6,7,V,5,8,8,0,6,4,5,7,7,16,14,18,0,6,6,8,7,10,16,14,18,V,4,V,2,V,1,V,6,V,5,V,3,V,7,V,8,V,9,a,1,=6,a,2,=4,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=9,a,8,=7,a,9,=4,a,10,=2,a,11,=4,拓扑序列：,V,1,V,2,V,6,V,8,V,4,V,9,V,3,V,7,V,5,执行上课礼，不迟到、不早退、不旷课,10,课上不吃早点、不玩手机、不睡觉,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,活动,e l,0,0,0,2,6,6,4,6,5,8,7,7,7,7,7,10,16,16,14,14,0,3,事件,Ve,Vl,V,1,0,0,V,2,3,4,V,6,2,2,V,8,6,6,V,4,6,7,V,9,8,8,V,3,6,6,V,7,6,7,V,5,8,8,0,6,4,5,7,7,16,14,18,0,6,6,8,7,10,16,14,18,V,4,V,2,V,1,V,6,V,5,V,3,V,7,V,8,V,9,a,1,=6,a,2,=4,a,3,=5,a,4,=1,a,5,=1,a,6,=2,a,7,=9,a,8,=7,a,9,=4,a,10,=2,a,11,=4,ek=,vei,lk,=,vlj,dut,(),说明：,1,、并不是加快任何一个关键活动都可以缩短整个工程的工期。只有加快那些包括在所有关键路径上的关键活动才能达到这个目的。,2,、,关键活动的速度提高是有限度的。,执行上课礼，不迟到、不早退、不旷课,11,课上不吃早点、不玩手机、不睡觉,最短路径,在非网图中,，最短路径是指两顶点之间经历的,边数,最少的路径,在网图中,，最短路径是指两顶点之间经历的,边上权值之和,最短的路径,B,A,E,D,C,B,A,E,D,C,10,50,30,10,100,20,60,AE：100,ADE：90,ADCE：60,ABCE：70,AE：1,ADE：2,ADCE：3,ABCE：3,执行上课礼，不迟到、不早退、不旷课,12,课上不吃早点、不玩手机、不睡觉,最短路径问题,1.,求图中某顶点到其余各顶点的最短路径问题，也称为单源最短路径问题,2.,求每对顶点之间的最短路径问题,求解算法,单源最短路径,Dijkstra,算法,任意顶点对之间的最短路径,Floyd,算法,执行上课礼，不迟到、不早退、不旷课,13,课上不吃早点、不玩手机、不睡觉,迪杰斯特拉提出了一个,按路径长度递增的次序,求从源点到其余各点最短路径的算法。,单源最短路径问题,A,B,A,E,D,C,10,50,30,10,100,20,60,S=A,AB:(A,B)10,AC,:(A,C),AD:,(A,D)30,AE:,(A,E)100,S=A,B,B,AC,:(A,B,C)60,S=A,B,D,D,AC,:(A,D,C)50,AE:,(A,D,E)90,S=A,B,D,C,C,AE:,(A,D,C,E)60,E,S=A,B,D,C,E,执行上课礼，不迟到、不早退、不旷课,14,课上不吃早点、不玩手机、不睡觉,13,8,30,32,V2:8,13,-,13,30,32,V1:13,-,-,13,30,28,20,V3:13,-,-,-,19,28,20,V4:19,终点 从,V0,到各终点的最短路径及其长度,V1,V2,V3,V4,V5,V6,Vj,-,-,-,-,2,7,20,V6:20,V,5,V,1,V,6,V,4,V,3,V,2,V0,8,5,6,8,30,13,7,5,32,15,示例：,0,13,8,Inf,30,Inf,32,;,Inf,0,Inf,Inf,Inf,9,7,;,Inf,Inf,0,5,Inf,Inf,Inf,;,Inf,Inf,Inf,0,6,Inf,Inf,;,Inf,Inf,Inf,Inf,0,2,Inf,;,Inf,Inf,Inf,Inf,Inf,0,17,;,Inf,Inf,Inf,Inf,Inf,Inf,0,5,执行上课礼，不迟到、不早退、不旷课,15,课上不吃早点、不玩手机、不睡觉,每对顶点之间的最短路径,方法,1,：每次以一个顶点为源点，,调用,n,次,Dijkstra,算法求解，,时间复杂度为,O(n,3,),。,方法,2,：弗洛伊德算法,(1962),N,个顶点的图中，最短路径的长度小于,N,顶点,i,到顶点,j,的最短路径：每个顶点都可能成为中间顶点,以邻接矩阵作为图的存储结构,时间复杂度是,O(n,3,),执行上课礼，不迟到、不早退、不旷课,16,课上不吃早点、不玩手机、不睡觉,弗洛伊德算法的基本思想,对于从,vi,到,vj,的弧，,进行,n,次试探,：首先考虑路径,vi,v,0,vj,是否存在，如果存在，则比较,vi,vj,和,vi,v,0,vj,的路径长度，取较短者为从,vi,到,vj,的中间顶点的序号不大于,0,的最短路径。在路径上再增加一个顶点,v,1,，依此类推，在经过,n,次比较后，最后求得的必是从顶点,vi,到顶点,vj,的最短路径。,执行上课礼，不迟到、不早退、不旷课,17,课上不吃早点、不玩手机、不睡觉,Floyd,算法求最短路径,B,A,C,6,3,4,11,2,4 11,6 2,3 ,(a),路径长度,AB AC,BA BC,CA,(b),路径,加入顶点,A,4 11,6 2,3,7,(a),路径长度,AB AC,BA B