系统集成项目管理工程师培训关键路径.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.8 关键路径,问题:,假设以有向网表示一个施工流图，弧上的权值表示完成某活动所需时间问：哪些活动是“关键活动”？,即：哪些活动将影响整个工程的完成期限的？,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,6,1,7,4,活动,事件,1,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,2,4,4,6,1,4,7,“,关键活动,”指的是,：该弧上的,权值增加,将使有向图上的,最长路径的长度增加,整个工程完成的时间为,：从有向图的,源点,到,汇点,的最长路径源点,汇点,7,2,如何求关键活动？,“,活动,(弧)”的,最早开始时间,e(i),“,活动,(弧)”的,最迟开始时间,l(i),关键活动,：e(i)l(i),“,事件,(顶点)”的,最早发生时间,ve(j),“,事件,(顶点)”的,最迟发生时间,vl(k),假设第 i 条弧为 则 对第 i 项活动言,e(i)=ve(j)；,l(i)=vl(k)dut()；,j,k,i,a,b,c,e,6,4,1,1,6,1,3,事件(顶点)发生时间的计算公式,最早开始时间：,ve(源点)=0；,ve(k)=Maxve(j)+dut(),最迟开始时间：,vl(汇点)=ve(汇点)；,vl(j)=Minvl(k)dut(),a,b,c,e,6,4,1,1,6,1,4,a,b,c,d,e,f,g,h,k,6,4,5,2,1,1,8,7,2,4,4,0,0,0,0,0,0,0,0,0,6,4,5,7,11,5,7,15,14,18,18,18,18,18,18,18,18,18,18,16,14,8,6,6,10,8,0,7,拓扑有序序列:,a-d-f-c-b-e-h-g-k,5,0,6,4,5,7,7,15,14,18,18,14,16,10,7,8,6,6,0,0,0,0,6,4,5,7,7,7,15,14,14,16,0,2,3,6,6,8,8,7,10,6,算法的实现,求ve的顺序应该是按拓扑排序的次序；,求vl的顺序应该是按拓扑逆序的次序；,因为拓扑逆序序列即为拓扑有序序列的逆序列，,因此应该在拓扑排序的过程中，另设一个“栈”记下拓扑有序序列。