5.4.4 关键路径

在带权有向图中，以顶点表示时间，有向边表示活动，边上的权值表示完成该活动的开销（如完成活动所需的时间），则称这种有向图为用边表示活动的网络，简称为AOE网。

①只有在某顶点所代表的时间发生或，从该顶点出发的各有向边所代表的活动才能开始。

②只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的时间才能发生。

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始。

网中也仅存在一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

在AOE网中，有些活动是可以并行进行的。从源点到汇点的邮箱路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需要的时间虽然不同，但是只有所有路径上的活动都完成了整个工程才能算是结束了。因此，从源点到灰顶的所有路径中，具有最大路径长度的路径称为关键路径。把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度，也就是关键路径上个活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即如果关键路径不能按时完成的话，整个工程的完成时间就会延长。因此只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

寻找关键活动时所用到的参量定义：

1、事件Vk的最早发生时间ve(k)

它是从开始顶点V到Vk的最长路径长度，事件的最早发生时间决定了所有从Vk开始的活动能够开工的最早时间。

ve(源点)=0

ve(k)=MAX{ve(j)+Weight(vj,vk)}，Weight(vj,vk)表示<vj，vk>上的权值

注意：在计算ve(k)时，是按从前往后的顺序来计算的。

2.时间Vk的最迟发生时间vl(k)

它是指在不推迟整个工程完成的前提下，即保证它所指向的事件vi在ve(i)时刻能够发生时，该时间最迟必须发生的时间。

vl(汇点)=ve(汇点)

vl(j)=Min{vl(k)-Weight(vj，vk)}，Weight(vj,vk)表示<vj，vk>上的权值

注意：在计算vl(k)时，是按从后往前的顺序来计算的。

3.活动ai的最早开始时间

它是指该活动的起点所表示的事件最早发生时间。如果边<vk，vj>表示活动ai，则有e(i)=ve(k)

4.活动ai的最迟开始时间

它是指该活动的终点所表示的事件最迟发生时间与该活动所需的时间之差。如果边<vk，vj>表示活动ai，则有l(i)=vl(j)-Weight(vk,vj).

5.一个活动ai的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i)

它是指活动完成的时间余量，是在不增加完成整个工程所需的总时间的情况下，活动ai可以拖延的时间。如果一个活动的时间余量为0时，说明该活动必须要如期完成，否则会拖延整个工程的进度，所以称l(i)-e(i)=0,即l(i)=e(i)的活动ai是关键活动。

求关键路径的算法步骤如下：

1）求AOE网中所有时间的最早发生时间ve().

2）求AOE网中所有时间的最迟发生时间vl().

3）求AOE网中所有活动的最早发生时间v().

4）求AOE网中所有活动的最迟发生时间l().

5）求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。

1）关键路径上的所有活动都是关键路径，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定程度，该关键活动可能变成非关键活动了。

2）网中的关键路径并不唯一。且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快这些包括在所有关键路径上的关键活动才能达到缩短工期的目的。