图关键路径
关键路径就是完成这项工程最久的那条路径，可能会有多条
关键路径不同于求最早完成时间或者最晚完成时间，还要求出路径上都有哪些值和边。如果是单纯求最早/最晚完成时间时间，可以通过拓扑排序后，对每个顶点动态规划，求每个顶点的最早/最晚完成时间。
求关键路径一般应用于aoe网，其实就是求出每个点的最早和最晚开始时间，如果两者相等，这个点就是关键路径的点。注意这里的最晚开始时间是通过整个ddl从后往前计算的。 后面可以不看。
如果是aov网，也可以一样逻辑的。
AOE网
AOE 网是在 AOV 网的基础上，其中每一个边都具有各自的权值，是一个有向无环网。其中权值表示活动持续的时间。
图 1 AOE网
如图 1 所示就是一个 AOE 网，例如 a1=6 表示完成 a1 活动完成需要 6 天；AOE 网中每个顶点表示在它之前的活动已经完成，可以开始后边的活动，例如 V5 表示 a4 和 a5 活动已经完成，a7 和 a8 可以开始。
使用 AOE 网可以帮助解决这样的问题：如果将 AOE 网看做整个项目，那么完成整个项目至少需要多少时间？
解决这个问题的关键在于从 AOE 网中找到一条从起始点到结束点长度最长的路径，这样就能保证所有的活动在结束之前都能完成。
起始点是入度为 0 的点，称为“源点”；结束点是出度为 0 的点，称为“汇点”。这条最长的路径，被称为”关键路径“。
因此关键路径是通过并行完成某些边然后完成所有边的最长路。关键路径：从源点到汇点具有最大长度的路径。这个概念要清楚，一个工程不一定有一条关键路径，可能会有多条。
AOV和AOE的区别：
1.AOV用顶点表示活动的网，描述活动之间的制约关系。
2.AOE用边表示活动的网，边上的权值表示活动持续的时间。
AOE 是建立在子过程之间的制约关系没有矛盾的基础之上，再来分析整个过程需要的时间。
为了求出一个给定 AOE 网的关键路径，需要知道以下 4 个统计数据：
- 对于 AOE 网中的顶点有两个时间：最早发生时间（用 Ve(j) 表示）和最晚发生时间（用 Vl(j) 表示）；
- 对于边来说，也有两个时间：最早开始时间（用 e(i) 表示）和最晚开始时间（ l(i) 表示）。
Ve(j)：对于 AOE 网中的任意一个顶点来说，从源点到该点的最长路径代表着该顶点的最早发生时间，通常用 Ve(j) 表示。
例如，图 1 中从 V1 到 V5 有两条路径，V1 作为源点开始后，a1 和 a2 同时开始活动，但由于 a1 和 a2 活动的时间长度不同，最终 V1-V3-V5 的这条路径率先完成。但是并不是说 V5 之后的活动就可以开始，而是需要等待 V1-V2-V5 这条路径也完成之后才能开始。所以对于 V5 来讲，Ve(5) = 7。
Vl(j)：表示在不推迟整个工期的前提下，事件 Vk 允许的最晚发生时间。
例如，图 1 中，在得知整个工期完成的时间是 18 天的前提下，V7 最晚要在第 16 天的时候开始，因为 a10 活动至少需要 2 天时间才能完成，如果在 V7 事件在推迟，就会拖延整个工期。所以，对于 V7 来说，它的 Vl(7)=16。
e(i)：表示活动 ai 的最早开始时间，如果活动 ai 是由弧 <Vk,Vj> 表示的，那么活动 ai 的最早开始的时间就等于时间 Vk 的最早发生时间，也就是说：e[i] = ve[k]。
e(i)很好理解，拿图 1 中 a4 来说，如果 a4 想要开始活动，那么首先前提就是 V2 事件开始。所以 e[4]=ve[2]。
l(i)：表示活动 ai 的最晚开始时间，如果活动 ai 是由弧 <Vk,Vj> 表示，ai 的最晚开始时间的设定要保证 Vj 的最晚发生时间不拖后。所以，l[i]=Vl[j]-len<Vk,Vj>。
在得知以上四种统计数据后，就可以直接求得 AOE 网中关键路径上的所有的关键活动，方法是：对于所有的边来说，如果它的最早开始时间等于最晚开始时间，称这条边所代表的活动为关键活动。由关键活动构成的路径为关键路径。
举个例子
说明：上图中J中为49，是最早开始时间。这里可以看到最早开始时间，就是完要成该顶点，前面的所有到该点的路径都要已经完成。所以取路径最大那一条。
补充说明：
事件最早开始时间：例子图中，F点，ACF（9） 和 ADF（19），到达F点时候，保证AC和AD都完成，这样 F才能开始，所以F点的最早开始时间取最大值，即19 可以看出，要求出到某一点的最早开始时间，则需要将汇于该点的所有路径的时间求出来，取最大值。
事件最迟开始时间：这里是反着推，比如H点最迟开始时间，H到J 与 H到I到J两条路径，39 和 44，所谓最迟开始时间，就是超过这个时间就会影响整个工程进度，而这个时间是时间点，是从源点工程开始计时的，所以对于H点，39和44是相对于源点，如果取44，则H-J这条路径就会拖延，最迟开始时间选择最小值。
关键路径上的顶点与顶点之间的活动的应该最早开始和最迟开始时间是相等的，如果不等那么说明活动还有余额时间（在最早开始时间和最迟开始时间之间可以任选一个时间点开始），这说明还有其他活动是决定这个工程时间的，那就不是关键路径了。
算法思想：
要准备两个数组，a：最早开始时间数组etv，b：最迟开始时间数组。（针对顶点即事件而言）
1.从源点V0出发，令etv[0]（源点）=0，按拓扑有序求其余各顶点的最早发生时间etv[i]（1 ≤ i ≤ n-1）。同时按照上一章
拓扑排序的方法检测是否有环存在。
2.从汇点Vn出发，令ltv[n-1] = etv[n-1]，按拓扑排序求各个其余各顶点的最迟发生时间ltv[i]（n-2 ≥ i ≥ 2）;
3.根据各顶点的etv和ltv数组的值，求出弧（活动）的最早开工时间和最迟开工时间，求每条弧的最早开工时间和最迟开工时间是否相等，若相等，则是关键活动。
注意：1，2 完成点（事件）的最早和最迟。3根据事件来计算活动最早和最迟，从而求的该弧（活动）是否为关键活动。
已知点的第一个和最后一个的最早开始时间和最晚开始时间都是相等的。
因此先求出第一个点到最后一个点的拓扑排序，然后根据拓扑排序递推可以求出每个点的最早开始时间。
每个点的最早开始时间= max(前置点的最早开始时间)
按拓扑排序的倒序可递推可以求出每个点的最晚开始时间，此时最后一个点的最早开始时间已经求出了，那最后一个点的最晚开始时间就是最早开始时间。
每个点的最晚开始时间=max(next点最晚开始时间-边长度)
求出每个点的最早开始时间和最晚开始时间后，就已知边的最早和最晚开始时间， 边最早就是前面点最早，边最晚就是后面点最晚减去边长度。
在得知以上四种统计数据后，就可以直接求得 AOE 网中关键路径上的所有的关键活动，方法是：对于所有的边来说，如果它的最早开始时间等于最晚开始时间，称这条边所代表的活动为关键活动。由关键活动构成的路径为关键路径。