C语言AOE网、关键路径

1.AOE网（Activity On Edge Network）

若在带权的有向图中，用有向边表示活动（子工程），边上的权值表示活动持续时间，即完成该活动所需时间；用顶点表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此均已完成，它的所有出边活动就此开始这样一种状态，则成此带权的有向图为用边表示活动的网，简称AOE网。

（1）源点（起点）：表示整个工程的开始，只有出边，没有入边

（2）汇点（终点）：表示整个工程的结束，只有入边，没有出边

源点到汇点的所有路径中最长的路径长度（路径上各边的权值和）称为关键路径（Critical Path）。关键路径也指完成工程的最短时间。

（1）Ve（j）：时间Vj的最早发生时间，即源点V1到汇点Vj的最长路径长度

（2） C语言AOE网、关键路径：活动的最早发生时间。 = Ve（j）。（活动：所有以Vj为起点的各条出边<Vj, Vk>表示的活动）

（3）Vl（k）：事件Vk的最迟发生时间。等于汇点Vn的最早发生时间Ve（n）减去Vk到Vn的最长路径长度

（4） C语言AOE网、关键路径：活动的最迟开始时间。等于的最迟完成时间减去的持续时间： = Vl（k）- dur（< j, k >）

（5） C语言AOE网、关键路径：活动的时间余量。 = -

（6）dur（< j, k >）：活动 C语言AOE网、关键路径的持续时间（活动：边<Vj, Vk>表示的活动）

（7）关键活动：活动的时间余量为0的活动。即 C语言AOE网、关键路径 = - = 0

（1）计算事件Vj的最早、最晚发生时间Ve（j）、Vl（j）

从源点V1自左向右计算。Ve（1）= 0，Ve（j）= max{ Ve（i）+ dur（< i, j >） }

从汇点Vn自右到左计算。Vl（n）= Ve（n），Vl（j）= min{ Vl（k）- dur（< j, k >） }

（2）计算活动 C语言AOE网、关键路径（边<Vj, Vk>表示的活动）的最早发生、最迟开始时间、

C语言AOE网、关键路径 = Ve（j）， = Vl（k）- dur（< j, k >）

（3）确定关键路径

首先：计算活动 C语言AOE网、关键路径的时间余量 = -

其次：找出 C语言AOE网、关键路径 = 0 的活动

所有 C语言AOE网、关键路径 = 0 的活动的路径集合即为AOE网中的关键路径。

C语言AOE网、关键路径