算法有向无环图及其应用关键路径.pptx
1 关键路径关键路径1.问题提出 假设以有向网表示一个施工流图，假设以有向网表示一个施工流图，用顶点表用顶点表示事件，弧表示活动；示事件，弧表示活动；弧上的权值表示完成该项弧上的权值表示完成该项子工程所需时间。子工程所需时间。每个事件表示在它之前的活动每个事件表示在它之前的活动已完成，在它之后的活动可以开始已完成，在它之后的活动可以开始.第1页/共19页2例例 设一个工程有设一个工程有11项活动，项活动，9个事件个事件事件事件 V1表示整个工程开始表示整个工程开始事件事件V9表示整个工程结束表示整个工程结束问题：（问题：（1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4关键路径关键路径(Critical Path)汇点源点第2页/共19页3AOE(Activity On Edges)AOE(Activity On Edges)网络:如果在带权DAGDAG图中 用有向边表示一个工程中的活动(Activity)Activity)用边上权值表示活动持续时间(Duration)Duration)用顶点表示事件(Event)Event)则这样的有向图叫做用边表示活动的网络，简称 AOE AOE(Activity On Edges)(Activity On Edges)网络。2.定义定义第3页/共19页路径长度：从源点到汇点可能有多条有向路径，路径上各活动所需 时间之和叫该路径的路径长度关键路径：具有最大路径长度的路径叫做关键路径，上图的关键路 径有a1,a4,a7,a10和 a1,a4,a8,a11,它们的路径长度均为18关键活动：关键路径上的所有活动都叫做关键活动，对上图的AOE，关键活动是a1,a4,a7,a8,a10,a11 关键活动上持续时间的变化可能影响整个工程的工期987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4汇点源点第4页/共19页5路径长度路径上各活动持续时间之和关键路径路径长度最长的路径Ve(j)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(i)-e(i)表示完成活动ai的机动时间关键活动关键路径上的活动，即l(i)=e(i)的活动关键路径关键路径(Critical Path)AOE中有关概念中有关概念第5页/共19页63.如何找e(i)=l(i)的关键活动？设活动设活动ai用弧用弧表示，其持续时间表示，其持续时间记为：记为：dut()则有：则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkai如何求Ve(j)和Vl(j)？第6页/共19页7如何求Ve(j)和Vl(j)？关键路径关键路径(Critical Path)(1)从ve(1)=0开始向前递推j(2)从vl(n)=ve(n)开始向后递推i第7页/共19页84.4.求关键路径步骤（1）求Ve(i)（2）求Vl(j)（3）求e(i)（4）求l(i)（5）计算l(i)-e(i)关键路径关键路径(Critical Path)第8页/共19页987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4汇点源点 事件V Vi i的最早可能开始时间VeiVei：是从源点V V1 1到顶点V Vi i的最长路径长度。如Ve5=6+1=7Ve5=6+1=7 事件V Vi i的最迟允许开始时间VliVli：是工程按期完成情况下V Vi i的最迟允许开始时间。如Vl5=18 (4+7)=7Vl5=18 (4+7)=7，Vl6=18 (4+4)=10 Vl6=18 (4+4)=10 活动a ak k的最早可能开始时间ekek：设a ak k是在 V 上，ekek是从源点到V Vi i的最长路径长度，故ek=Veiek=Vei，例如，e4=Ve2=6 e4=Ve2=6，e6=Ve4=5e6=Ve4=5第9页/共19页987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4汇点源点 活动ak的最迟允许开始时间lk：是工程按期完成情况下ak的最迟允许开始时间，设ak在上，并ak的持续时间为dur()，lk=Vlj-dur()。例如，l4=Vl5-dur()=7 1=6 l6=Vl6-dur()=10 2=8 活动ak的机动时间：是lk ek，例如 a6的机动时间l6 e6=8 5=3 a4的机动时间l4 e4=6 6=0，关键活动上有lk=ek第10页/共19页11987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动活动 e l l-e 00002266046258377077071031616014140033例例（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkai第11页/共19页125.算法思想（1）建立AOE网；（2）从源点v0出发，令ve0=0，边进行拓扑排序，边计算其余各顶点的vei。若图中有回路则结束（3）从汇点vn-1出发,vln-1=eln-1,按逆拓扑有序的顺序求vli,i=n-2,0。（4）根据各点的ve和vl值，求每条弧的最早开始时间e(s)和最迟开始时间 l(s)。若某弧满足条件 e(s)=l(s)，则是关键活动。关键路径关键路径(Critical Path)第12页/共19页136.6.求关键路径算法：求关键路径算法：在此算法中需要对邻接表中单链表的结在此算法中需要对邻接表中单链表的结点加以修改点加以修改,在各结点中增加一个在各结点中增加一个intint域域 infoinfo,记录该边的权值。记录该边的权值。关键路径关键路径(Critical Path)第13页/共19页14拓扑排序算法（计算拓扑排序算法（计算拓扑排序算法（计算拓扑排序算法（计算veve）：）：）：）：status topLogicalSort(ALGraph G,Stack&t)FindInDegree(G,indegree);for(k=0;knextarc)k=p-adjvex;if(-indegreek=0)push(S,k);/入度为入度为0则入栈；则入栈；if(vej+*(p-info)vek)vek=vej+*(p-info);/for /while if(countadjvex;dut=*(p-info);if(vlk-dutvlj)vlj=vlkj-dut;/for p /while jkjkkk第15页/共19页16/求求ee,el和关键活动和关键活动 for(j=0;jadjvex;dut=*(p-info);ee=vej;el=vlk-dut;if(ee=el)tag=*;else tag=;printf(j,k,dut,ee,el,tag);/for p /criticalPath jk第16页/共19页第17页/共19页18 在拓扑排序求在拓扑排序求 vei 和逆拓扑有序求和逆拓扑有序求 vli 时时,所需时间为所需时间为O(n+e),求各个活动的求各个活动的 ek和和 lk时所需时间为时所需时间为O(e),总共花费时间仍然是总共花费时间仍然是O(n+e)。7.分析时间复杂度分析时间复杂度第18页/共19页感谢您的观看！第19页/共19页
