AOE的处理——关键路径CPM

Critical Path Method

关键路径法是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种
AOE网

AOE网是带权的有向无环图，通常用来估算项目进程或完成的时间其中：
顶点：Vi表示事件
边： ai表示活动
边权： weight表示活动持续的时间

关键路径概念
关键路径：从源点到汇点的最长路径叫做关键路径，其路径长度是该路径上活动持续时间之和，也是工程完成的最少时间

事件最早发生时间Ve(i)： 从源点到事件Vi的最长路径长度，称为Vi的最早发生时间。决定了Vi之后的活动的最早开始时间.

事件最迟发生时间Ve(i)： 不影响整个工期进度，而Vi可以最迟发生的时间，用Vl(i)表示

活动最迟开始时间： 活动ai最早可以开始进行的时间，用e(i)表示

活动最迟开始时间： 在不推迟整个工程完成的前提下，活动ai最迟必须开始的时间，用l（i）表示。

关键活动： 活动时间余量为0的活动，即l（i）-e（i）=0的活动，关键路径上的所有活动都是关键活动.

非关键活动： 不在关键路径上的活动.

算法思想：

1 建立AOE网的邻接表和逆邻接表
2 计算事件最早发生时间：
设置Ve(1),Ve(2).....Ve(n)=0,从原点出发，
按照拓扑序列计算Ve(j),若拓扑序列中的顶点数等于n，转第三步3，
否则AOE网中有回路，不能求得关键路径，算法终止
3 计算事件最迟发生时间：
置Vl(1),vl(2),Vl(3),vl(n)=Ve(n)从汇点出发按逆拓扑序列求Vl(i)
4 由Ve(j)和vl(j)求e(i)和l(i)
5 找出e(i)=l(i)的活动，并输出之，从而确定关键路径

时间复杂度：O(|V|+|E|)

算法：


暂时先把代码贴在这，回头考完再来整理！