AOE网与关键路径

AOE网与关键路径

1.AOE网：在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间

（1）源点：整个工程的开始点，其入度为0

（2）终点：整个工程的结束点，其出度为0

（3）性质：

• 只有进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生
• 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始

（4）AOE网能够解决什么问题？

• 完成整个工程至少需要多少时间
• 为缩短完成工程所需的时间， 应当加快哪些活动? 

（5）最短工期：从源点到终点的最大路径长度

---

2.关键路径（不唯一）：具有最大路径长度的路径，关键路径上的活动称为关键活动

（1）求最短工期——>求关键路径——>求关键活动

   关键活动为什么关键？

• 开始时间不能推迟
• 最早开始时间和最晚开始时间相等

（2）设带权有向图 G=(V，E)含有 n 个顶点 e 条边，设置 4 个一维数组：

• 事件的最早发生时间 ve[n]
• 事件的最迟发生时间 vl[n]
• 活动的最早开始时间 ae[e]
• 活动的最晚开始时间 al[e]

（3）事件的最早发生时间 ve[n]

    ve[0] = 0

    ve[k] = max{ve[j] + len} (∈p[k])    

    p[k]：所有到达 vk 的有向边

    按拓扑顺序求，max（起点+权值）

（4）事件的最迟发生时间 vl[n]

    vl[n-1] = ve[n-1]

    vl[k] = min{vl[j]-len}（∈s[k]）

    s[k] ：所有从 vk 发出的有向边

    逆拓扑序求，min（终点-权值）

（5）活动的最早开始时间 ae[e]

    起点最早

（6）活动的最晚开始时间 al[e]

    终点最迟-权值

---

3.一些说法

（1）若任意一个关键活动延期，则工期一定延长

（2）若任意一个关键活动加快，则工期不一定加快

（3）若任意一个非关键活动延期，则工期可能延长

（4）若任意一个非关键活动延期，则工期不加快