第二十九讲关键路径

1、数,据,结,构,第,二十九,讲,知,识,点,活动的最早开始时间、最迟开始时间,关键活动、关键路径的确定,最短路径的概念,从源点到各顶点最短路径算法的描述,每两个顶点间最短路径的查找,重,点,关键路径中各顶点与活动最早开始时间和,最迟开始时间的确定,从源点到各顶点最短路径求解过程,数,据,结,构,7,、在描述关键路径的算法时，设活动,a,由弧,表示，持续时间记为,dut,，则,1,）事件,Vj,的最早出现时间,vej,从源点,V0,到某顶点,Vj,的最长路径长度叫作事件,Vj,的,最早开始时间，,vej=maxvei+dut,，,?,T,必须在拓扑有序前提下进行,2,）活动,a,的最早开始时间,

2、eei,顶点,Vj,的最早出现时间,vej,决定了从,Vj,指出的各条边,所代表活动的最早开始时间，显然,eei= vej,。,数,据,结,构,3,）事件,Vk,的最迟开始时间,vlk,vlk=minvlp-dut,?,T,必须在拓扑逆序前提下进行,(4),活动,a,的最迟开始时间,el,eli=vlk-dut,(5),只要某活动,a,i,有,eei=eli,的关系，我们就称,a,i,为关键活动。关键路径上各条边所对应的活动,都是关键活动。,数,据,结,构,V2,V1,V3,V5,V4,V6,V1,V3,V4,V6,顶点,ve vl,活动,e l l-e,v1,v2,v3,v4,v5,v6,a

3、1,a2,a3,a4,a5,a6,a7,a8,0,0,3,4,2,6,6,8,2,6,7,8,0,0,3,3,2,2,6,6,1,1,0,4,4,2,5,6,7,0,1,1,0,3,0,1,数,据,结,构,V2,V1,V3,V5,V4,V6,v6,v4,v5,v2,v3,v1,T,数,据,结,构,T,T,v4,v5,S,v4,v2,v3,v1,T,S,T,v6,S,v6,v5,v4,v2,v3,v1,T,v3,v2,S,v3,v1,v1,T,v3,v2,v1,S,v4,v5,v2,S,v2,v3,v1,v6,v5,v5,v4,v2,v3,v1,数,据,结,构,7,7,最短路径,如果从图中某顶点

4、出发（此点称为源点），经图的,边到达另一顶点（称为终点）的路径不止一条，如,何找到一条路径使沿此路径上各边的权值之和为最,小。,7,7,1,从源点到其余顶点的最短路径,?,迪杰斯特拉算法（,P190,）,用集合,S,记住已找到从,v,出发找到最短路径,的终点的集合，一开始,S,中只包括顶点,v,，,用,T,记住剩下的顶点。,数,据,结,构,?,若图中有边,v,v,j,则,v,j,的距离为此边,的权值，否则,v,j,的距离值为一个很大的数，,?,每次从,T,的顶点中选一个其距离值最小的,Vm,加入到，,S,中。每往,S,加入一个顶点,Vm,，就要对,T,的各个顶,点,的距离值进行一次修正。若加进

5、,Vm,做中间顶点,使从,v,到,V,j,的最短路径比不加,Vm,的路径为短,则,要修改,Vj,的距离值。修改后再选距离最小的顶点,加入到,S,中。,?,如此进行下去，直到图中所有顶点都包括在,S,中，,或再也没有可加入到,S,中的顶点存在为止。,数,据,结,构,V0,V5,V4,V2,V1,V3,20,30,终,点,i=1,i=2,i=3,i=4,i=,5,v,1,?,?,?,?,?,v,2,10,(v0,v2),v,3,?,60,(v0,v2,v3),50,(v0,v4,v3),v,4,30,(v0,v4),30,(v1,v4),v,5,100,(v0,v5),100,(v0,v5),90

6、,(v0,v4,v5),60,(v0,v4,v3,v5),v,j,v2,v4,v3,v5,S,v0,v2,v0,v2,v4,v0,v2,v3,v4,v0,v2,v3,v4,v5,数,据,结,构,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,v4,T,T,v5,T,T,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,选,中,V2,绿,色,为,被,复,制,的,内,容,Pv2=v0,v2,，,Pv3=Pv2+v3,，,Pv4=v0,v4,，,Pv5=v0,v5,（,1,）,（,2,）,红色字体,表示复制,绿色部分,数,据,结,构,

7、选,中,V4,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv4+v5,Pv2=v0,v2,，,Pv3=Pv2+v3,，,Pv4=v0,v4,，,Pv5=v0,v5,（,2,）,（,3,）,数,据,结,构,选,中,V3,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,T,v0,v1,v2,v3,

8、v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv4+v5,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv3+v5,（,3,）,（,4,）,数,据,结,构,v0,v1,v2,v3,v4,v5,v1,v2,T,T,v3,T,T,T,v4,T,T,v5,T,T,T,T,从上图看到，,Pvv,为,T,，表示找到从源点,V0,到顶点,V,的最短路径，,Pv2=v0,v2,，,Pv4=v0,v4,Pv3=Pv2+v3=v0,v2,v3,Pv5= P

9、v3+v5=v0,v2,v3,Pv2=v0,v2,，,Pv3=Pv4+v3,，,Pv4=v0,v4,，,Pv5=Pv3+v5,（,4,）,数,据,结,构,7,7,2,从每对顶点间的最短路径,?,弗洛伊德算法（,P192,）,?,如果从顶点,vi,到顶点,vj,有弧，则从顶点,vi,到顶,点,vj,存在一条长度为,Costij,的路径，该路径,不一定是最短路径，尚需进行,n,次试探。,?,首先考虑路径（,vi,，,v0,，,vj,）是否存在（即判,断弧（,vi,，,v0,）和（,v0,，,vj,）是否存在）。如,果存在，则比较（,vi,，,v0,，,vj,）和（,vi,，,vj,）的,路径长度，

10、然后取长度较短者为顶点,vi,到顶点,vj,的中间顶点的序号不大于,0,的最短路径。,数,据,结,构,?,假如在路径上再增加一个顶点,v1,，也如果,（,vi,，,，,v1,）和（,v1,，,，,vj,）分别是,当前找到的中间顶点的序号不大于,0,的最,短路径，那么（,vi,，,，,v1,，,，,vj,）,就有可能是从,vi,到顶点,vj,的中间顶点的序,号不大于,l,的最短路径。,数,据,结,构,将它和已经得到的从,vi,到顶点,vj,的中间顶点序,号不大于,0,的最短路径相比较，从中选出中,间顶点的序号不大于,1,的最短路径之后，再,增加一个顶点,v2,，继续进行试探。依次类推,长度较短者便是从顶点,vi,到顶点,vj,的中间序号,不大于,k,的最短路径。,经过,n,次比较后，最后求得的必是从顶点,vi,到,顶点,vj,的最短路径。,数,据,结,构,v0,v1,v2,6,4,3,11,2,a,b,c,顶点间经过,顶点的序号,?,-1,不存在,顶点间经过,顶点的序号,?,0,既,v0,顶点间经过顶,点的序号,?,1,既,v0,v1,顶点间经过顶点,的序号,?,2,，