Question

拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。比如说，造一辆汽车，我们需要先造各种各样的零件、部件，最终再组装成车，如图7-9-1所示。这些零部件基本都是在流水线上同时生产的，假如造一个轮子需要0.5天时间，造一个发动机需要3天时间，造一个车底盘需要2天时间，造一个外壳需要2天时间，其他零部件时间需要2天，全部零部件集中到一处需要0.5天，组装成车需要2天时间，请问，在汽车厂造一辆车，最短需要多少时间呢？

图7-9-1

有人说时间就是全部加起来，这当然是不对的。我已经说了前提，这些零部件都是分别在流水线上同时生产的，也就是说，在生产发动机的3天里，可能已经生产了6个轮子，1.5个外壳和1.5个底盘，而组装车是在这些零部件都生产好后才可以进行。因此最短的时间其实是零部件中生产时间最长的发动机3天+集中零部件0.5天+组装车的2天，一共5.5天完成一辆汽车的生产。

因此，我们如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。

因此在前面讲了AOV网的基础上，我们来介绍一个新的概念。在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Net-work）。我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE网只有一个源点一个汇点。例如图7-9-2就是一个AOE网。其中v₀即是源点，表示一个工程的开始，v₉是汇点，表示整个工程的结束，顶点v₀，v₁，……，v₉分别表示事件，弧<v₀,v₁>，<v₀,v₂>，……，<v₈,v₉>都表示一个活动，用a₀，a₁，……，a₁₂表示，它们的值代表着活动持续的时间，比如弧<v₀,v₁>就是从源点开始的第一个活动a₀，它的时间是3个单位。

图7-9-2

既然AOE网是表示工程流程的，所以它就具有明显的工程的特性。如有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生。

尽管AOE网与AOV网都是用来对工程建模的，但它们还是有很大的不同，主要体现在AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动持续的时间，如图7-9-3所示两图的对比。因此，AOE网是要建立在活动之间制约关系没有矛盾的基础之上，再来分析完成整个工程至少需要多少时间，或者为缩短完成工程所需时间，应当加快哪些活动等问题。

图7-9-3

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。显然就图7-9-3的AOE网而言，开始→发动机完成→部件集中到位→组装完成就是关键路径，路径长度为5.5。

如果我们需要缩短整个工期，去改进轮子的生产效率，哪怕改动成0.1也是无益于整个工期的变化，只有缩短关键路径上的关键活动时间才可以减少整个工期长度。例如如果发动机制造缩短为2.5，整车组装缩短为1.5，那么关键路径长度就为4.5，整整缩短了一天的时间。

那么现在的问题就是如何找出关键路径。对人来说，图7-9-3第二幅这样的AOE网，应该比较容易得出关键路径的，而对于图7-9-2的AOE网，就相对麻烦一些，如果继续复杂下去，可能就非人脑该去做的事了。