7.9.2　关键路径算法

我们将图7-9-2的AOE网转化为邻接表结构如图7-9-4所示，注意与拓扑排序时邻接表结构不同的地方在于，这里弧链表增加了weight域，用来存储弧的权值。

7.9.2　关键路径算法 - 图1

7.9.2　关键路径算法 - 图2

图7-9-4

求事件的最早发生时间etv的过程，就是我们从头至尾找拓扑序列的过程，因此，在求关键路径之前，需要先调用一次拓扑序列算法的代码来计算etv和拓扑序列列表。为此，我们首先在程序开始处声明几个全局变量。

  1. int *etv, *ltv;    /* 事件最早发生时间和最迟发生时间数组 */
  2. int *stack2;       /* 用于存储拓扑序列的栈 */
  3. int top2;          /* 用于stack2的指针 */

其中stack2用来存储拓扑序列，以便后面求关键路径时使用。

下面是改进过的求拓扑序列算法。

  1. /* 拓扑排序，用于关键路径计算 */
  2. Status TopologicalSort(GraphAdjList GL)
  3.  {
  4.     EdgeNode *e;
  5.     int i, k, gettop;
  6.     /* 用于栈指针下标 */
  7.     int top = 0;                                              
  8.     /* 用于统计输出顶点的个数 */
  9.     int count = 0;                                            
  10.     /* 建栈将入度为0的顶点入栈 */
  11.     int *stack;                                               
  12.     stack = (int *)malloc(GL->numVertexes * sizeof(int));
  13.     for (i = 0; i < GL->numVertexes; i++)
  14.        if (0 == GL->adjList[i].in)
  15.            stack[++top] = i;
  16.     /* 初始化为0 */
  17.     top2 = 0;                                                 
  18.     /* 事件最早发生时间 */
  19.     etv = (int *)malloc(GL->numVertexes * sizeof(int));       
  20.     for (i = 0; i < GL->numVertexes; i++)
  21.         /* 初始化为0 */
  22.         etv[i] = 0;                                           \
  23.     /* 初始化 */
  24.     stack2 = (int *)malloc(GL->numVertexes * sizeof(int));    
  25.     while (top != 0)
  26.     {
  27.         gettop = stack[top--];
  28.         count++;
  29.         /* 将弹出的顶点序号压入拓扑序列的栈 */
  30.         stack2[++top2] = gettop;                              
  31.         for (e = GL->adjList[gettop].firstedge; e; e = e->next)
  32.         {
  33.             k = e->adjvex;
  34.             if (!(--GL->adjList[k].in))
  35.                 stack[++top] = k;
  36.             /* 求各顶点事件最早发生时间值 */
  37.             if ((etv[gettop] + e->weight) > etv[k])           
  38.                 etv[k] = etv[gettop] + e->weight;
  39.         }
  40.     }
  41.     if (count < GL->numVertexes)
  42.         return ERROR;
  43.     else
  44.         return OK;
  45. }

代码中，除加粗部分外，与前面讲的拓扑排序算法没有什么不同。

第11～15行为初始化全局变量etv数组、top2和stack2的过程。第21行就是将本是要输出的拓扑序列压入全局栈stack2中。第27～28行很关键，它是求etv数组的每一个元素的值。比如说，假如我们已经求得顶点v0对应的etv[0]=0，顶点v1对应的etv[1]=3，顶点v2对应的etv[2]=4，现在我们需要求顶点v3对应的etv[3]，其实就是求etv[1]+len<v1,v3>与etv[2]+len<v2,v3>的较大值。显然3+5<4+8，得到etv[3]=12，如图7-9-5所示。在代码中e->weight就是当前弧的长度。

7.9.2　关键路径算法 - 图3

图7-9-5

由此我们也可以得出计算顶点vk即求etv[k]的最早发生时间的公式是：

其中P[K]表示所有到达顶点vk的弧的集合。比如图7-9-5的P[3]就是<v1,v3>和<v2,v3>两条弧。len<vi,vk>是弧<vi,vk>上的权值。

下面我们来看求关键路径的算法代码。

  1. /* 求关键路径，GL为有向网，输出GL的各项关键活动 */
  2. void CriticalPath(GraphAdjList GL)
  3. {
  4.     EdgeNode *e;
  5.     int i, gettop, k, j;
  6.     /* 声明活动最早发生时间和最迟发生时间变量 */
  7.     int ete, lte;                                          
  8.     /* 求拓扑序列，计算数组etv和stack2的值 */
  9.     TopologicalSort(GL);                                   
  10.     /* 事件最晚发生时间 */
  11.     ltv = (int *)malloc(GL->numVertexes * sizeof(int));    
  12.     for (i = 0; i < GL->numVertexes; i++)
  13.         /* 初始化ltv */
  14.         ltv[i] = etv[GL->numVertexes - 1];                 
  15.     /* 计算ltv */
  16.     while (top2 != 0)                                      
  17.     {
  18.         /* 将拓扑序列出栈，后进先出 */
  19.         gettop = stack2[top2--];                           
  20.         for (e = GL->adjList[gettop].firstedge; e; e = e->next)
  21.         {                                                  
  22.             /* 求各顶点事件的最迟发生时间ltv值 */
  23.             k = e->adjvex;
  24.             /* 求各顶点事件最晚发生时间ltv */
  25.             if (ltv[k] - e->weight < ltv[gettop])          
  26.                 ltv[gettop] = ltv[k] - e->weight;
  27.         }
  28.     }
  29.     /* 求ete，lte和关键活动 */
  30.     for (j = 0; j < GL->numVertexes; j++)                  
  31.     {
  32.         for (e = GL->adjList[j].firstedge; e; e = e->next)
  33.         {
  34.             k = e->adjvex;
  35.             /* 活动最早发生时间 */
  36.             ete = etv[j];                                  
  37.             /* 活动最迟发生时间 */
  38.             lte = ltv[k] - e->weight;                      
  39.             * 两者相等即在关键路径上 */
  40.             if (ete == lte)                                /
  41.                 printf("<v%d,v%d> length: %d , ",
  42.                     GL->adjList[j].data, GL->adjList[k].data, e->weight);
  43.         }
  44.     }
  45. }

1．程序开始执行。第5行，声明了ete和lte两个活动最早最晚发生时间变量。

2．第6行，调用求拓扑序列的函数。执行完毕后，全局变量数组etv和栈stack的值如图7-9-6所示，top2=10。也就是说，对于每个事件的最早发生时间，我们已经计算出来了。

7.9.2　关键路径算法 - 图4

图7-9-6

3．第7～9行为初始化全局变量ltv数组，因为etv[9]=27，所以数组ltv当前的值为：{27,27,27,27,27,27,27,27,27,27}

4．第10～19行为计算ltv的循环。第12行，先将stack2的栈头出栈，由后进先出得到gettop=9。根据邻接表中，v9没有弧表，所以第13～18行循环体未执行。

5．再次来到第12行，gettop=8，在第13～18行的循环中，v8的弧表只有一条<v8,v9>，第15行得到k=9，因为ltv[9]-3<ltv[8]，所以ltv[8]=ltv[9]-3=24，如图7-9-7所示。

7.9.2　关键路径算法 - 图5

图7-9-7

6．再次循环，当gettop=7、5、6时，同理可算出ltv相对应的值为19、13、25，此时ltv值为：{27，27，27，27，27，13，25，19，24，27}

7．当gettop=4时，由邻接表可得到v4有两条弧<v4,v6>、<v4,v7>，通过第13～18行的循环，可以得到ltv[4]=min(ltv[7]-4,ltv[6]-9)=min(19-4,25-9)=15，如图7-9-8所示。

7.9.2　关键路径算法 - 图6

图7-9-8

此时你应该发现，我们在计算ltv时，其实是把拓扑序列倒过来进行的。因此我们可以得出计算顶点vk即求ltv[k]的最晚发生时间的公式是：

7.9.2　关键路径算法 - 图7

其中S[K]表示所有从顶点vk出发的弧的集合。比如图7-9-8的S[4]就是<v4,v6>和<v4,v7>两条弧，en<vk,vj>是弧<vk,vj>上的权值。

就这样，当程序执行到第20行时，相关变量的值如图7-9-9所示，比如etv[1]=3而ltv[1]=7，表示的意思就是如果时间单位是天的话，哪怕v1这个事件在第7天才开始，也可以保证整个工程的按期完成，你可以提前v1事件开始时间，但你最早也只能在第3天开始。跟我们前面举的例子，是先完成作业再玩还是先玩最后完成作业一个道理。

7.9.2　关键路径算法 - 图8

图7-9-9

8．第20～31行是来求另两个变量活动最早开始时间ete和活动最晚开始时间lte，并对相同下标的它们做比较。两重循环嵌套是对邻接表的顶点和每个顶点的弧表遍历。

9．当j=0时，从v0点开始，有<v0,v2>和<v0,v1>两条弧。当k=2时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[2]-len<v0,v2>=4-4=0，此时ete=lte，表示弧<v0,v2>是关键活动，因此打印。当k=1时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[1]-len<v0,v1>=7-3=4，此时ete≠lte，因此<v0,v1>并不是关键活动，如图7-9-10所示。

7.9.2　关键路径算法 - 图9

图7-9-10

这里需要解释一下，ete本来是表示活动<vk,vj>的最早开工时间，是针对弧来说的。但只有此弧的弧尾顶点vk的事件发生了，它才可以开始，因此ete=etv[k]。

而lte表示的是活动<vk,vj>的最晚开工时间，但此活动再晚也不能等vj事件发生才开始，而必须要在vj事件之前发生，所以lte=ltv[j]-len<vk,vj>。就像你晚上23点睡觉，你不能说到23点才开始做作业，而必须要提前2小时，在21点开始，才有可能按时完成作业。

所以最终，其实就是判断ete与lte是否相等，相等意味着活动没有任何空闲，是关键活动，否则就不是。10．j=1一直到j=9为止，做法是完全相同的，关键路径打印结果为“<v0,v2>4,<v2,v3>8,<v3,v4>3,<v4,v7>4,<v7,v8>5,<v8,v9>3,”，最终关键路径如图7-9-11所示。

7.9.2　关键路径算法 - 图10

图7-9-11

分析整个求关键路径的算法，第6行是拓扑排序，时间复杂度为O(n+e)，第8～9行时间复杂度为O(n)，第10～19行时间复杂度为O(n+e)，第20～31行时间复杂也为O(n+e)，根据我们对时间复杂度的定义，所有的常数系数可以忽略，所以最终求关键路径算法的时间复杂度依然是O(n+e)。

实践证明，通过这样的算法对于工程的前期工期估算和中期的计划调整都有很大的帮助。不过注意，本例是唯一一条关键路径，这并不等于不存在多条关键路径的有向无环图。如果是多条关键路径，则单是提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。这就像仅仅是有事业的成功，而没有健康的身体以及快乐的生活，是根本谈不上幸福的人生一样，三者缺一不可。