关键路径——C语言（理论）

关键路径，是项目网络中从起始事件到终止事件的最长路径，决定了项目的最短完成时间。

关键路径中的任务没有任何可调整的余地，如果任何一个任务被延迟，整个项目的完成时间也会被延迟。

假设我们现在有一个图：把图的边看作是活动，权值为活动的持续时间；图的顶点看作是事件，事件是指在项目中发生的关键时间点没有时间，即箭头的头是事件开始，箭头末尾是事件完成。这就是所谓的AOE图

在以前我们把边看作是距离，在这里我们把边看作是时间，即顶点到顶点所需的时间，那么接下来我们就要引出几个概念：

事件的最早开始时间和最晚开始时间

        我们假设顶点0是从时间为0时开始的，那么顶点1的最早开始时间为 6（因为需要经过时间为6的活动），顶点 2 为 4 ，顶点 3 为 5 。那么顶点 4 的最早起始时间是什么时候？因为要等活动全部进行完才可以进行下一个活动，所以顶点 4 的最早起始时间为 7，同样对于顶点 8 来说，有多条路径，但是要等前面所有活动都进行完，也就是取时间最长的，所以是（7+9+2）或者（7+7+4）路径而不是走顶点0，3，5，7，这样加起来是17<18。

所以事件（顶点）的最早开始时间为（从0到8）：

0，6，4，5，7，7，16，14，18

        接下来是最晚开始时间，最晚时间代表着在不延误项目的情况下，最晚开始的时间。对于最后的事件 8 ，最晚开始时间就是最早开始时间（意思就是后面没得可以做了，要立刻宣布项目的完成，所以最晚也是最早），所以事件 8 的最晚开始时间为 18。

        反推前面的事件，事件 6 的最晚开始时间为 18-2=16，事件 7 的最晚开始时间为 18-4=14，事件 5 的最晚开始时间为 14-4=10，事件 4 的最晚开始时间为 16-9=7 或者 14-7=7，事件 3 的最晚开始时间为 10-2=8，事件 2 和事件 1 的最晚开始事件为7-1=6，那么事件0的最晚开始时间为多少？是6-6=0，6-4=2，还是8-5=3？考虑到不能延误活动，应该是三个中最小的6-6=0。

所以事件的最晚开始时间为（从0到8）：

0，6，6，8，7，10，16，14，18

当事件的最早开始时间和最晚开始时间相等时叫做关键事件，这代表着此事件是项目的关键项目，不可拖延。

活动的最早开始事件和最晚开始事件

        对于活动来说，最早开始时间就是箭头起始事件的最早开始时间，意味着这时已经可以开始进行活动了，所以对于ABC活动来说，最早开始时间都是0，D为6，E为4，F为5，那么GH的最早开始时间是多少?这里GH是事件4的最早开始事件，为7，以此类推。

最后，活动的最早开始时间，从（A到K）：

0，0，0，6，4，5，7，7，7，16，14

        最晚开始时间是箭头的终止事件的最晚开始时间减去权值，意味着这时必须要开始进行活动了，否则会延误，对于A来说，事件1的最晚开始时间为6，所以6-6=0，B，事件2的最晚开始时间为6，6-4=2，也就是说，B活动最晚要在时间为 2 的时候进行。以此类推。

最后，活动的最晚开始时间，从（A到K）：

0，2，3，6，6，8，7，7，10，16，14

讲完这两个概念，才到文章的主题：关键路径。

        关键路径是指活动的最早开始时间减去最晚开始时间为0的活动，也就是没有时间余量。我们可以发现 ADGHJK 活动是最早开始时间等于最晚开始时间的，所以这就是关键路径，如图：

        因为关键路径是最短完成项目的事件，所以在优化项目的时候要着重优化这几个活动，从而提高效率，这就是关键路径的意义。

现在我们可以先思考一下代码的过程：

1.拓扑排序，因为最早最晚时间要考虑前驱后继（事件）

2.计算事件的最早最晚时间，根据是否相等确定关键路径上的事件。

3.找出关键路径

完整的代码会在下一篇文章，希望对你有所帮助，如有错误欢迎指出。