数据结构与算法—关键路径

《数据结构与算法—关键路径》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关键路径若在带权的有向图中，以顶点表示事件，以冇向边表示活动，边上的权值表示活动的开销(如该活动持续时间)，则此带权的冇向图称为边表示活动的网(ActivityonEdgeNetwork),简称AOE网。【例】图7.21是一个网。其中有9个事件vl,v2,...,v9；11项活动a1,a2,...,a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如vl表示整个工程开始,v9表示整个工程结束。V5表示活动a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动al需耍6天时间可以完成。(1)AOV网具有的性质1.只有在某顶点所代表的事

2、件发生后，从该顶点出发的各有向边所代表的活动才能开始。2.只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。3.表示实际工程计划的AOE网应该是无坏的，并且存在唯一的入度过为()的开始顶点和唯一的出度为0的完成顶点。(2)由事件vj的最早发生时间和最晚发生时间的定义，可以采取如下步骤求得关键活动：1.从开始顶点vl出发，令ve(l)=0,按拓扑有序序列求其余各顶点的可能最早发生时间。Ve(k)=max{ve(j)+dut()}(7.1)j三T其中T是以顶点vk为尾的所有弧的头顶点的集合(2

3、,则说明网中有环，不能求岀关键路径，算法结束。2.从完成顶点vn出发，令vl(n)=vc(n),按逆拓朴有序求其余各顶点的允许的最晚发牛时间：vl(j)=min{vl(k)-dut()}k£S其中S是以顶点vj是头的所有弧的尾顶点集合(1)o若某条弧满足e(i)=l(i),则它是关键活动。对于图7.21所示的AOE网,按以上步骤的计算结果见表7.3，可得到a1,a4,a7,a8,a10,all是关键活动。*1.3MA翊呵006640S671781

4、4141111U10迥%000••0220II*■t0■4fi1stI710710气78IJ7140■tl7U0(1)求出AOE网中所有关键活动后，只要删去AOE网中所有的非关键活动，即可得到AOE网的关键路径。这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图7.21的AOE网中有二条关键路径，(v1,v2,v5,v7,v9)和(vl,v2,v5,v8,v9)它们的路径长度都是16o如图7.24所示。B7J**阿耘MElWtS注意:并不是加快任何一个关键活动都可以缩短整个工程完成的时间，只有加快那些包括在所有的关键路径上的关键活动才能达到这个冃的。只

5、有在不改变AOE网的关键路径的前提下，加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间。关键路径1、AOE网用顶点表示事件，弧农示活动，弧上的权值表示活动持续的吋间的有向图叫AOE(ActivityOnEdgeNetwork)网。AOE网常用于估算工程完成时间。2、AOE网研究的问题(1)完成整个工程至少需要多少时间；(2)哪些活动是影响工程的关键。1956年，美国杜邦公司提岀关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。3、关键路径的几个术语(1)关键路径从源点到汇点的路径长度故长的路径

6、叫关键路径。(2)活动开始的最早时间e(i)(3)活动开始的最晚时间l(i)定义e(i)=l(i)的活动叫关键活动。(4)事件开始的最早时间ve(i)(5)事件开始的最晚时间vl(i)设活动ai由弧vj,k>(即从顶点j到k)表示，英持续时间记为dut(vj,k>),则e(i)=ve(j)l(i)=vl(k)-dut()(6_6_1)求ve(i)和vl(j)分两步：•从ve(1)=0开始向前递推ve(j)=Max{ve(i)+dut()}(6_6_2)T,2<=j<=n其中，T是所有以j为弧头的弧的集合。•从vl(n)=ve(n)开始向后递推vl(i)=Min{

7、vl(j)-dut()}(6_6_3)vi,j>S,1v=iv=n-1其中，S是所有以i为弧尾的弧的集合。两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。4、求关键路径的算法(1)输入e条弧vj,k>,建立AOE网的存储结构。(2)从源点v1出发，令ve⑴=0,求ve(j)2<=j<=n0(3)从汇点vn出发，令vl(n)=ve(n),求vl(i)l<=i<=n-1<>⑷根据药顶点的ve和vl值，