数据结构假设一个工程的进度计划用AOE网题，

Question

假设一个工程的进度计划用AOE网表示 1、求出每个事件的最早发生时间和最晚发生时间2、该工程完成至少需要多少时间3、求出所有关键路径和关键活动。（我没有问过问题没有多少分恳请学霸帮忙。）

Answer 1

关键路径的算法思想：
1>从ve[0]=0开始利用递推公式求出其余顶点的最早发生时间ve[j]
ve[j]=Max{ve[i]+dut<i,j>}
(i=0,1,2,….n-1 j=1,2,…n-1 <vj,vk>∈E )
即从源点开始按拓扑有序求各顶点的最早发生时间
2>从vl[n-1]=ve[n-1]开始利用递推公式求出其余顶点的最迟发生时间vl[j]； vl[j]=Min{vl[k]-dut<j,k>}
3>求出每条弧(即活动)的最早开始时间e[i]与最迟开始时间l[i]
e[i]=ve[j]; l[i]=vl[k]-dut<vj,vk>
若 e[i]=l[i]即为关键活动。由关键活动组成的路径即关键路径
v1最早发生时间:ve[1]=ve[0]+a1=0+5=5;
v2最早发生时间:ve[2]=ve[0]+a2=0+6=6;
v3最早发生时间:有两条路v0->v1->v3,路径长度为5+3=8；v0->v2->3, 路径长度为6+12=18；取最大的即公式中的Max{ve[i]+dut<i,j>}的含义ve[3]=18
ve[4]=18+3=21;ve[5]=21;ve[6]=23;ve[7]=25;ve[8]=28;ve[9]=30;
假定vl[l]=ve[9]=30反向递推其余顶点的最迟发生时间
vl[8]=vl[9]-a14=30-2=28;
vl[7]=vl[8]-a13=28-2=26;
vl[6]=vl[8]-a12=28-5=23;
vl[5]=26;
vl[4]有两路：vl[6]-a9=22;vl[7]-a10=26-10=16取最小的16
其他依次类推：然后是
3>求出每条弧(即活动)的最早开始时间e[i]与最迟开始时间l[i]
e[i]=ve[j]; l[i]=vl[k]-dut<vj,vk>
找到 e[i]=l[i]的活动即关键活动。由关键活动组成的路径即关键路径追问

多谢前辈！！！懂了！！！！！

追答

客气了，不好意思！

Answer 2

这里错了 vl[4]有两路：vl[6]-a9=22;vl[7]-a10=26-10=16取最小的16，
a10=4