数据结构：关键路径

关键路径一种进度分析技术，用于在工程计划中估算完成整项工程至少需要多少时间、判断哪些活动是影响工程进度的关键等。在项目管理中，关键路径具有重要意义。它决定着项目的最短工期，因此项目经理需要重点关注关键路径上的所有活动，确保它们按时完成，以避免整个项目进度的延误。可以说，了解关键路径的概念和算法对于解决实际问题具有重要意义。

一、基本概念

1.1、AOE网

AOE网（Activity On Edge），是指以边表示活动的网。AOE网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE网可用来估算工程的完成时间。

例如，下图所示为一个有11项活动的AOE网。其中有9个事件 $v_0,v_1,...,v_8$ ，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。比如， $v_0$ 表示整个工程开始， $v_8$ 表示整个工程结束， $v_4$ 表示 $a_4$ 和 $a_5$ 已经完成， $a_7$ 和 $a_8$ 可以开始了。与每个活动相联系的数是执行该活动所需的时间，比如，活动 $a_1$ 需要6天， $a_2$ 需要4天等。

1.2、关键路径

在工程计划中，工程进度控制的关键在于抓住关键活动。在一定范围内，非关键活动的提前完成对于整个工程的进度没有直接的好处，它的稍许拖延也不会影响整个工程的进度。工程的指挥者可以把非关键活动的人力和物力资源暂时调给关键活动，加速其进展速度，以使整个工程提前完工。由于整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下，网中只有一个入度为零的点，称作源点，也只有一个出度为零的点，称作汇点。

在AOE网中，一条路径各弧上的权值之和称为该路径的带权路径长度（后面简称路径长度）。要估算完成整项工程的最短时间，就是要找一条从源点到汇点的带权路径长度最长的路径，称为关键路径（Critical Path）。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键，它们的提前或拖延将使整个工程提前或拖延。

例如，在前面的AOE网中， $v_0$ 是源点， $v_8$ 是汇点，关键路径有两条： $(v_0,v_1,v_4,v_6,v_8)$ 或 $(v_0,v_1,v_4,v_7,v_8)$ ，长度均为18。关键活动为 $(a_1,a_4,a_7,a_{10})$ 或 $(a_1,a_4,a_8,a_{11})$ 。比如，关键活动 $a_1$ 需要6天完成，如果 $a_1$ 提前1天，整个工程也可以提前1天完成。所以不论是估算工期，还是研究如何加快工程进度，主要问题就在于要找到AOE网的关键路径。

二、求解过程

2.1、关键路径的4个描述量

确定关键路径，需要先定义4个描述量。

事件 $v_i$ 的最早发生时间ve(i)

进入事件 $v_i$ 的每一活动都结束， $v_i$ 才可发生，所以ve(i)是从源点到 $v_i$ 的最长路径长度。

求ve(i)的值，可根据拓扑顺序从源点开始向汇点递推。通常将工程的开始顶点事件 $v_0$ 的最早发生时间定义为0，即

ve(0)=0

ve(i)=Max\{ve(k)+w_{k,i}\} \quad <v_k,v_i> \in T,1 \le i \le n-1

其中，T是所有以 $v_i$ 为头的弧的集合， $w_{k,i}$ 是弧 $<v_k,v_i>$ 的权值，即对应活动 $<v_k,v_i>$ 的持续时间。

事件 $v_i$ 的最迟发生时间vl(i)

事件 $v_i$ 的发生不得延误 $v_i$ 的每一后继事件的最迟发生时间。为了不拖延工期， $v_i$ 的最迟发生时间不得迟于其后继事件 $v_k$ 的最迟发生时间减去活动 $<v_i，v_k>$ 的持续时间。

求出ve(i)后，可根据逆拓扑顺序从汇点开始向源点递推，求出vl(i)。即

vl(n-1)=ve(n-1)

vl(i)=Min\{vl(k)-w_{i,k}\} \quad <v_i,v_k> \in S,0 \le i \le n-2

其中，S是所有以 $v_i$ 为尾的弧的集合， $w_{i,k}$ 是弧 $<v_i,v_k>$ 的权值。

活动 $a_i=<v_j,v_k>$ 的最早开始时间e(i)

只有事件 $v_j$ 发生了，活动 $a_i$ 才能开始。所以，活动 $a_i$ 的最早开始时间等于事件 $v_j$ 的最早发生时间 $ve(j)$ ，即

e(i)=ve(j)

活动 $a_i=<v_j,v_k>$ 的最晚开始时间l(i)

活动 $a_i$ 的开始时间需保证不延误事件 $v_k$ 的最迟发生时间。所以活动 $a_i$ 的最晚开始时间l(i)等于事件 $v_k$ 的最迟发生时间 $vl(k)$ 减去活动 $a_i$ 的持续时间 $w_{j,w}$ ，即：

l(i)=vl(k)-w_{j,k}

显然，对于关键活动而言，e(i)=l(i)。对于非关键活动，l(i)-e(i)的值是该工程的期限余量，在此范围内的适度延误不会影响整个工程的工期。

一个活动的最迟开始时间l(i)和其最早开始时间e(i)的差值l(i)-e(i)是该活动完成的时间余量。它是在不增加完成整个工程所需的总时间的情况下，该活动可以拖延的时间。当一个活动的时间余量为零时，说明该活动必须如期完整，否则就会拖延整个工程的进度。所以称l(i)−e(i)=0，即l(i)=e(i)的活动是关键活动。

2.2、求解关键路径的过程

知道了如何确定关键路径，就能给出求解关键路径的过程了，该过程如下：

对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)。
按逆拓扑序列求出每个事件的最迟发生时间vl(i)。
求出每个活动 $a_i$ 的最早开始时间e(i)。
求出每个活动 $a_i$ 的最晚开始时间l(i)。
找出e(i)=l(i)的活动，即关键活动。由关键活动形成的从源点到汇点的每一条路径就是关键路径，关键路径有可能不止一条。

2.3、计算关键路径的示例

例如，对前面的AOE网，计算其关键路径，过程如下。

计算各顶点事件 $v_i$ 的最早发生时间ve(i)。

ve(0) = 0
ve(1) = max{ve(0) + $w_{0,1}$ } = 6
ve(2) = max{ve(0) + $w_{0,2}$ } = 4
ve(3) = max{ve(0) + $w_{0,3}$ } = 5
ve(4) = max{ve(1) + $w_{1,4}$ , ve(2) + $w_{2,4}$ } = 7
ve(5) = max{ve(3) + $w_{3,5}$ } = 7
ve(6) = max{ve(4) + $w_{4,6}$ } = 16
ve(7) = max{ve(4) + $w_{4,7}$ , ve(5) + $w_{5,7}$ } = 14
ve(8) = max{ve(6) + $w_{6,8}$ , ve(7) + $w_{7,8}$ } = 18

计算各顶点事件 $v_i$ 的最迟发生时间ve(i)。

vl(8) = ve(8) = 18
vl(7) = min{vl(8) - $w_{7,8}$ } = 14
vl(6) = min{vl(8) - $w_{6,8}$ } = 16
vl(5) = min{vl(7) - $w_{5,7}$ } = 10
vl(4) = min{vl(6) - $w_{4,6}$ , vl(7) - $w_{4,7}$ } = 7
vl(3) = min{vl(5) - $w_{3,5}$ } = 8
vl(2) = min{vl(4) - $w_{2,4}$ } = 6
vl(1) = min{vl(4) - $w_{1,4}$ } = 6
vl(0) = min{vl(1) - $w_{0,1}$ , vl(2) - $w_{0,2}$ , vl(3) - $w_{0,3}$ } = 0

计算各活动 $a_i$ 的最早开始时间e(i)。

e( $a_1$ ) = ve(0) = 0
e( $a_2$ ) = ve(0) = 0
e( $a_3$ ) = ve(0) = 0
e( $a_4$ ) = ve(1) = 6
e( $a_5$ ) = ve(2) = 4
e( $a_6$ ) = ve(3) = 5
e( $a_7$ ) = ve(4) = 7
e( $a_8$ ) = ve(4) = 7
e( $a_9$ ) = ve(5) = 7
e( $a_{10}$ ) = ve(6) = 16
e( $a_{11}$ ) = ve(7) = 14

计算各活动 $a_i$ 的最迟开始时间l(i)。

l( $a_{11}$ ) = vl(8) - $w_{7,8}$ = 14
l( $a_{10}$ ) = vl(8) - $w_{6,8}$ = 16
l( $a_9$ ) = vl(7) - $w_{5,7}$ = 10
l( $a_8$ ) = vl(7) - $w_{4,7}$ = 7
l( $a_7$ ) = vl(6) - $w_{4,6}$ = 7
l( $a_6$ ) = vl(5) - $w_{3,5}$ = 8
l( $a_5$ ) = vl(4) - $w_{2,4}$ = 6
l( $a_4$ ) = vl(4) - $w_{1,4}$ = 6
l( $a_3$ ) = vl(3) - $w_{0,3}$ = 3
l( $a_2$ ) = vl(2) - $w_{0,2}$ = 2
l( $a_1$ ) = vl(1) - $w_{0,1}$ = 0

顶点的发生时间和活动的开始时间可分别汇总为如下两个表：

可以看出，在前面的AOE网中，有两条关键路径：一条是由活动 $(a_1,a_4,a_7,a_{10})$ 组成的关键路径，另一条是由 $(a_1,a_4,a_8,a_{11})$ 组成的关键路径，如下图所示。

三、算法实现

由于每个事件的最早发生时间ve(i)和最迟发生时间vl(i)要在拓扑序列的基础上进行计算，所以实现关键路径算法要基于拓扑排序算法。采用邻接表作为有向图的存储结构，实现关键路径算法要引入以下辅助的数据结构。

一维数组ve[i]：事件 $v_i$ 的最早发生时间。
一维数组vl[i]：事件 $v_i$ 的最迟发生时间。
一维数组topo[i]：记录拓扑序列的顶点序号。

实现关键路径算法的步骤为：

调用拓扑排序算法，将拓扑序列保存在一维数组topo中。
将每个事件的最早发生时间ve[i]初始化为0，即ve[i]=0。
根据一维数组topo中的值，按从前向后的拓扑次序，依次求每个事件的最早发生时间，循环n次，执行以下操作：
- 取得拓扑序列中的顶点序号k，即k=topo[i]；
- 用指针p依次指向k的每个邻接顶点，取得每个邻接点的序号j=p->adjvex，依次更新顶点j的最早发生时间ve[j]：

if(ve[j]<ve[k]+p->weight) \quad ve[j]=ve[k]+p->weight;

将每个事件的最迟发生时间vl[i]初始化为汇点的最早发生时间，vl[i]=ve[n-1]。
根据一维数组topo中的值，按从后向前的逆拓扑次序，依次求每个事件的最迟发生时间，循环n次，执行以下操作：
- 取得拓扑序列中的顶点序号k，即k=topo[i]；
- 用指针p依次指向k的每个邻接顶点，取得每个邻接点的序号j=p->adjvex，依次根据k的邻接点，更新k的最迟发生时间vl[k]：

if(vl[k]>vl[j]-p->weight) \quad vl[k]=vl[j]-p->weight;

判断某一活动是否为关键活动，循环n次，执行以下操作：
- 对于每个顶点 $v_i$ ，用指针p依次指向 $v_i$ 的每个邻接点，取得每个邻接点的序号j=p->adjvex，分别计算活动 $<v_i,v_j>$ 的最早和最迟开始时间e和l：
$e=ve[i];l=vl[j]-p->weight;$
- 如果e和l相等，则活动 $<v_i,v_j>$ 为关键活动，输出弧 $<v_i,v_j>$ 。

关键路径算法的C语言描述如下：

// 有向网G的存储结构为邻接表，输出其关键活动
Status CriticalPath(ALGraph G) {
    // 对G进行拓扑排序，将拓扑序列保存在topo中
    // 若调用失败，说明存在有向环，返回ERROR
    if(!TopologicalOrder(G,topo)) return ERROR;
    // n为顶点个数
    n=G.vexnum;

    // 将每个事件的最早发生时间初始化为0
    for(i=0;i<n;i++) ve[i]=0;
    // 按拓扑次序求每个事件的最早发生时间
    for(i=0;i<n;i++) {
        // 取得拓扑序列中的顶点序号k
        k=topo[i];
        // p指向k的第一个邻接点
        p=G.vertices[k].firstarc;
        // 依次更新k的所有邻接点的最早发生时间
        while(p!=NULL) {
            // j为邻接点的序号
            j=p->adjvex;
            // 更新顶点j的最早发生时间ve[j]
            if(ve[j]<ve[k]+p->weight)
                ve[j]=ve[k]+p->weight;
            // p指向k的下一个邻接点
            p=p->nextarc;
        }
    }

    // 将每个事件的最迟发生时间初始化为ve[n-1]
    for(i=0;i<n;i++) vl[i]=ve[n-1];
    // 按逆拓扑次序求每个事件的最迟发生时间
    for(i=n-1;i>=0;i--) {
        // 取得拓扑序列中的顶点序号k
        k=topo[i];
        // p指向k的第一个邻接点
        p=G.vertices[k].firstarc;
        // 依次更新k的所有邻接点的最迟发生时间
        while(p!=NULL) {
            // j为邻接点的序号
            j=p->adjvex;
            // 更新顶点j的最迟发生时间vl[k]
            if(vl[k]>vl[j]-p->weight)
                vl[k]=vl[j]-p->weight;
            // p指向k的下一个邻接点
            p=p->nextarc;
        }
    }

    // 判断某一活动是否为关键活动
    // 每次循环针对以vi作为活动开始点的所有活动
    for(i=0;i<n;i++) {
        // p指向i的第一个邻接点
        p=G.vertices[i].firstarc;
        while(p!=NULL) {
            // j为i的邻接顶点的序号
            j=p->adjvex;
            // 计算活动<vi,vj>的最早开始时间
            e=ve[i];
            // 计算活动<vi,vj>的最迟开始时间
            l=vl[j]-p->weight;
            // 若为关键活动，则输出<vi, vj>
            if(e==l) cout<<G.vertices[i].data<<G.vertices[j].data;
            // p指向i的下一个邻接点
            p=p->nextarc;
        }
    }
}

在求每个事件的最早和最迟发生时间，以及活动的最早和最迟开始时间时，都要对所有顶点及每个顶点边表中所有的边结点进行检查，由此，求关键路径算法的时间复杂度为 $O(n+e)$ 。

经实践证明：用AOE网来估算某些工程完成的时间是非常有用的。实际上，求关键路径的方法最初就是与维修和建造工程一起发展的。由于网中各项活动是互相牵涉的，因此，影响关键活动的因素亦是多方面的，任何一项活动持续时间的改变都可能引起关键路径的改变。所以，当子工程在进行过程中持续时间有所调整时，就要重新计算关键路径。另外，若网中有几条关键路径，那么，单是提高一条关键路径上关键活动的速度，还不能导致整个工程缩短工期，而必须同时提高在几条关键路径上的活动速度。