关键路径

AOE网：

AOV网：顶点便是活动，用弧表示活动间的优先关系
AOE网：顶点表示事件（通常是瞬间的事件），边表示活动
example：

性质：

源点和汇点:

关键路径/关键活动：

定义：

事件va的最早发生时间：

活动的最早开始时间e(i)：

事件vk的最迟发生时间()：

活动ai的最迟开始时间l(i）：

活动余量di：

活动余量=最最迟开始时间-最早开始时间
时间余量为零的点为关键活动，找到关键活动则找到关键路径

关键活动和关键路径的特性：

对于上例只改变一条关键路径的关键活动的时间（炒菜除外），不能减少其消耗时间，同时改变所有关键路径的时间才可以；或者改变关键路径共有的关键活动（炒菜），也可见压缩时间。

求解关键路径：

①求事件的最早发生时间

使用拓扑排序：对入度为零的点逐一排序

②求事件的最迟发生发生时间：

使用逆拓扑排序：对出度为零的顶点逐一排序

汇点的最迟发生时间和最早发生时间相同

③求所有活动的最早发生时间

④求所有活动的最迟发生时间

弧头所指事件的最晚发生事件-该活动所需时间

⑤求剩余余量

⑥寻找关键路径

剩余余量为零所对应的路径为关键路径，V1➡V3➡V4➡V6

总结：