ACM选讲-关键路径 ACM选讲-关键路径 定义 点到项点v最长径长度。即它前面工期全邮完成雷要的 <i>的边,D[为路征长度 计算 ·在不推个工期的提下最烟可以什么时候开始 从Ⅵ(1)=VE(m-1)即从最后一个工往前推 VLO=MinVLO-DOGJX <ij∈图的边集,D[[为径长度 图论习题课 ACM选讲-关键路径 图论习题课 6160,1,4,6,7,8 完 510 两条关键路径 谢谢 01468 38 01478 图论习题课 图论习题课7 图论习题课 ACM选讲-关键路径 „ 定义 „ 最早完成时间E(i) „ 从开始点到顶点Vi最长路径长度。即它’前面’工期全部完成需要的 时间。 „ 最晚完成时间L(i) „ 在不推迟整个工期的前提下，Vi最迟可以什么时候开始。 „ 关键活动 „ E(i)==L(i). 特点：‘前面’工期完成后，它必须马上开始，否则将延迟整个工期的 完成。 图论习题课 ACM选讲-关键路径 „ 计算E(i) 从VE(0)=0开始向前推： VE(j)=Max{VE(i)+D[i][j]} <i,j>∈图的边集，D[i][j]为路径长度 计算L(i) 从VL(n-1)=VE(n-1).即从最后一个工程往前推 VL(i)=Min{VL(j)-D[i][j]} <i,j>∈图的边集，D[i][j]为路径长度 图论习题课 ACM选讲-关键路径 E(i) 0 0 1 6 2 4 3 5 4 7 5 7 6 16 7 14 8 18 L(i) 8 18 7 14 6 16 5 10 4 7 3 8 2 6 1 6 0 0 有6个关键活动 0 ，1， 4， 6， 7， 8 两条关键路径 0 1 4 6 8 0 1 4 7 8 图论习题课 图论习题课 完 谢 谢