图解：什么是关键路径？

小禹禹，五一假期马上结束了，你们过得怎么样呢？有没有玩得很开心，收获满满呢？好想听你们在评论区说一说。哈哈，不过我们还是先来说一说今日景禹要给你们分享的内容，关键路径。何为关键路径？如果...

ZenjaminFranklin

39874人浏览 · 2020-05-06 20:31:39

ZenjaminFranklin · 2020-05-06 20:31:39 发布

小禹禹，五一假期马上结束了，你们过得怎么样呢？有没有玩得很开心，收获满满呢？好想听你们在评论区说一说。哈哈，不过我们还是先来说一说今日景禹要给你们分享的内容，关键路径。何为关键路径？如果在一个有向无环图中求得关键路径？关键路径又有什么作用呢？且听景禹慢慢道来。

前言

昨日景禹在写拓扑排序的时候提到，拓扑排序是关键路径的基础，那么为什么这么说呢？相信小禹禹看完文章定能有所感悟。在此之前我们看一些简单但很重要的概念。

什么是AOE网？

AOE网（Activity On Edge）即边表示活动的网，是与AOV网（顶点表示活动）相对应的一个概念。而拓扑排序恰恰就是在AOV网上进行的，这是拓扑排序与关键路径最直观的联系。AOE网是一个带权的有向无环图，其中顶点表示事件（Event），弧表示活动，权表示活动持续的时间。（小禹禹心想，这不就等于没说吗？看过后就没了印象）。景禹给大家备好了图，下面的就是一个AOV网：

其中表示事件，表示活动，活动的取值表示完成该活动所需要的时间，如表示完成活动所需要的时间为6天。此外，每一事件表示在它之前的活动已经完成，在它之后的活动可以开始，如表示活动和已经完成，活动和可以开始了。

什么是AOE网的源点和汇点？

由于一个工程中只有一个开始点和一个完成点，故将AOE网中入度为零的点称为源点，将出度为零的点称为汇点。

打个比方，我们现在有一个工程，就是将大象装进冰箱，那么源点就相当于我们现在接到这样一个任务，而汇点则表示我们完成了这个任务。那么我们之前所讲的打开冰箱门，将大象装进去，关上冰箱门就属于活动本身（即所表示的信息），打开冰箱门所需要的时间就是活动所需要的时间，而完成某一个活动所到达的顶点就表示一个事件（冰箱门打开）。下图中的红色顶点表示源点，表示汇点。

什么是关键路径呢？

举个栗子。

唐僧师徒从长安出发去西天取经，佛祖规定只有四人一起到达西天方能取得真经。假如师徒四人分别从长安出发，走不同的路去西天：孙悟空一个筋斗云十万八千里，一盏茶的功夫就到了；八戒和沙和尚稍慢点也就一天左右的时间；而唐僧最慢需要14年左右。徒弟到达后是要等着师傅的。那么用时最长的唐僧所走的路，就是取经任务中的关键路径。其他人走的路径属于非关键路径。

由于AOE网中的有些活动是可以并行进行的（如活动、和就是可以并行进行的），所以完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径就叫做 关键路径（Critical Path）。如下图中红色顶点和有向边构成的就是一条关键路径，关键路径的长度就是完成活动、和、所需要的时间总和，即为 6+1+9+2 = 18.

我向小禹禹现在对于关键路径、源点、汇点、事件、活动和AOE网有了一个清晰的认识，但我们要想在一个有向图当中找到这样一条关键路径还得清楚下面的四个概念。

小禹禹：我的天，一个关键路径光概念就这么多，还好景禹讲得清楚，不然我早跪了。

景禹：哈哈，因为关键路径有用呀，她难免身加很多 “光环” ，小禹禹看完文章一定会佩服自己并感慨关键路径的，我们一起来看四个重要的概念呗！

什么是ETV?

ETV（Earliest Time Of Vertex)：事件最早发生时间，就是顶点的最早发生时间；(看图说话)

事件的最早发生时间表示从源点出发到达顶点经过的路径上的权值之和，从源点出发到达顶点只经过了权值为6的边，则的最早发生时间为6，表示在活动完成之后，事件才可以开始；同理，事件要发生（即最早发生）需要活动和活动完成之后才可以，故事件的最早发生时间为 5 + 2 = 7。其他顶点（事件）的最早发生时间同理可的。需要说明，事件的最早发生时间一定是从源点到该顶点进行计算的。

什么是LTV?

LTVLatest Time Of Vertex)：事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间，如果超出此时间将会延误整个工期。

前面景禹在谈关键路径的概念时给出了一条上图中的关键路径，该关键路径（，，，，）的长度为18，为什么要提这个长度呢，因为要计算某一个事件的最晚发生时间，我们需要从汇点进行倒推。计算顶点的最晚发生时间为例，已知关键路径的长度为18，事件到汇点所需要的时间为 1 + 9 + 2 = 12，则事件的最晚发生时间为18-12 = 6，聪明的小禹禹一定发现，这和事件的最早发生时间不是一样吗？的确如此，对于关键路径上的顶点都满足最早发生时间 etv 等于最晚发生时间 ltv 的情况，这也是我们识别关键活动的关键所在。再来计算一下事件的最晚发生时间，事件到汇点所需要的时间为 4 + 4 = 8，则事件的最晚发生时间为 18 - 8 = 10；相当于说活动完成之后，大可以休息 3天，再去完成活动也不会影响整个工期。

什么是ETE?

ETE(Earliest Time Of Edge)：活动的最早开工时间，就是弧的最早发生时间。

活动要最早开工时间为事件的最早发生时间 6；同理，活动的最早发生时间为事件的最早发生时间 7。显然活动的最早开工时间就是活动发生前的事件的最早开始时间。

什么是LTE?

LTE(Lastest Time of Edge)：活动的最晚发生时间，就是不推迟工期的最晚开工时间。

活动的最晚发生时间则是基于事件的最晚发生时间。比如活动的最晚发生时间为事件的最晚发生时间减去完成活动所需时间，即 7 - 1 = 6；活动的最晚发生时间为事件的最晚发生时间减去完成活动所需时间，即 14 - 4 = 10；

从上面也就可以看出 只要知道了每一个事件（顶点）的ETV 和 LTV，就可以推断出对应的 ETE 和 LTE . 此外还需要注意，关键路径是活动的集合，而不是事件的集合，所以当我们求得 ETV 和 LTV 之后，还需要计算 ETE 和 LTE 。

关键路径算法

求关键路径的过程事实上最重要的就是上面提到的四个概念，ETV、LTV、ETE 和 LTE，求得了ETE与LTE之后只需要判断两者是否相等，如果相等则为关键路径中的一条边，则输出。为了清晰的明白算法的执行流程，我们一起 Step By Step.

首先求事件的最早发生事件ETV，这里使用的就是之前分享的拓扑排序，我们也走一遍，算是对拓扑排序的回顾。不清楚的小禹禹可以回头看看之前的文章图解：什么是拓扑排序？

第一步，建立图所对应的邻接表。

拓扑排序获得每一个事件的最早发生时间

初始时将ETV当中的数据都设置为0：

下面开始便是拓扑排序的过程了。

第二步：将入度为零的顶点入栈；

第三步：顶点出栈，并遍历顶点的邻接顶点，即 index 分别为 1，2，3 的顶点、和顶点，并将邻接顶点的入度减1，判断是否为 0 ，如果为 0 则入栈。首先遍历 index = 1 顶点，并将顶点的入度减 1 ，发现为零，则将顶点入栈，判断 ETV[0] + w( ) 是否大于 ETV[1] , 发现大于，则将 ETV[1] 更新为 ETV[0] + w( ) = 6；同理遍历 index = 2 的顶点，将顶点入栈，并将 ETV[2] 更新为 4 ；遍历 index = 3 的顶点，将顶点入栈，并将 ETV[3] 更新为 5 。

第四步：弹出栈顶元素并遍历顶点的邻接顶点 . 将顶点的入度减一，并将 ETV[5] 更新为 ETV[3] + ，即为7.

第五步：弹出栈顶元素并遍历邻接顶点 .

第六步：弹出栈顶元素，并遍历的邻接顶点 .

第七步：弹出栈顶元素 ,并遍历的邻接顶点 .

第八步：弹出栈顶元素 ,并遍历的邻接顶点和 .

第九步：弹出栈顶元素 ,并遍历的邻接顶点。

第十步：弹出栈顶元素 ,并遍历的邻接顶点。

第十一步：将栈顶元素出栈。

其中，我们将拓扑排序过程中的出栈序列依次入栈，即拓扑排序结束时，我们响应的保存了一个出栈序列，用于逆向计算事件的最晚发生时间：

根据事件的最早发生时间ETV推断事件的最晚发生时间 LTV

通过拓扑排序我们获得了每一个顶点的最早发生时间 ETV，紧接着便可以计算 LTV了。

计算LTV的值，即每一个顶点的最晚发生时间值，初始时将LTV的值初始化为汇点的时间 18 。

紧接着则是访问之前的出栈序列栈。

首先将顶点出栈，什么都不做。

第二步：将顶点出栈，并判断LTV[6] 与 LTV[8] - 的大小，将 LTV 更新为 LTV[8] - = 16

第三步：将顶点出栈，更新 LTV[7] 为 LTV[8] - = 14。

第三步：将顶点出栈，并遍历的邻接顶点和。用邻接顶点的LTV值减去活动的值，并与顶点的LTV值进行比较，将LTV[4] 更新为 7；同理用邻接顶点的LTV值减去活动的值，并与顶点的值进行比较，发现相等不做更新。

第四步，弹出栈顶元素 ,并遍历的邻接顶点 , 用顶点的LTV(最晚发生时间) 减去活动所需时间，即为6，将顶点的LTV[1] 更新为6.

第五步，弹出栈顶事件（顶点） ,并更新顶点的最晚发生时间。

第六步：弹出栈顶事件（顶点） .

第七步：弹出栈顶元素并更新其最晚发生时间。

第八步：弹出栈顶元素并更新其最晚发生时间。使用事件的最晚发生时间 6 减去活动所需时间6 等于0，与顶点的最晚时间相比较并更新为0。需要说明，事实上源点的最晚发生时间与最早发生时间都为0，毋庸置疑 。

此时我们得到每个事件（顶点）的最早发生时间和最晚发生时间，但 关键路径是活动的集合，所以接下来我们用事件的最早发生时间和最晚发生时间计算出活动（弧）的最早与最晚发生时间即可

计算活动的最早与最晚发生时间

第一步：从源点开始，遍历源点的邻接顶点 , 将弧 < > 上的活动的最早发生时间更新为源点的最早发生时间 0，将活动的最晚发生时间更新为事件的最晚发生时间 6 减去活动所需要的时间6，即为0. 判断活动的最早发生时间与最晚发生时间是否相等，如果相等则为关键活动，并输出。同理遍历源点的邻接顶点和，并更新弧和的最晚发生时间与最早发生时间。

第二步：访问顶点，遍历的邻接顶点 . 将活动的最早发生时间更新为事件的最早发生时间，将活动的最晚发生时间更新为事件的最晚发生时间 7 减去活动所需时间 1，即为6.

第三步：访问顶点，遍历的邻接顶点 . 将活动的最早发生时间更新为事件的最早发生时间 4 ，将活动的最晚发生时间更新为事件的最晚发生时间 7 减去活动所需时间 1，即为6.

第四步：访问顶点，遍历该顶点的邻接顶点，将活动的最早发生时间更新为事件的最早发生时间5，活动的最晚发生时间为事件的最晚发生时间10 减去活动所需要的时间 2，即为8.

第五步：访问顶点，并分别遍历该顶点的邻接顶点和顶点。将活动和的最早发生时间更新为时间的最早发生时间7，最晚发生时间也更新为7。

第六步：访问顶点，并遍历该顶点的邻接顶点，将活动的最早发生时间更新为事件的最早发生时间7，最晚发生时间更新为事件的最晚发生时间 14 减去活动所需时间4 ，即为10.

第七步：访问顶点，更新活动的最早发生时间和最晚发生时间。

第八步：访问顶点，更新活动的最早发生时间和最晚发生时间。

第九步：访问顶点，没有邻接顶点，什么都不做。

这样我们获得一个带权有向无环图中的关键路径：

接下来我们再看完整的代码，我相信小禹禹必定会了然于胸（如果还不懂，建议多点儿耐心，多看几遍景禹辛苦给小禹禹写的分析）。

// 边表结点声明
typedef struct EdgeNode
{
  int adjvex;
  struct EdgeNode *next;
}EdgeNode;

// 顶点表结点声明
typedef struct VertexNode
{
  int in; // 顶点入度
  int data;
  EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
  AdjList adjList;
  int numVertexes, numEdges;
}graphAdjList, *GraphAdjList;

int *etv, *ltv;
int *stack2; // 用于存储拓扑序列的栈
int top2; // 用于stack2的栈顶指针

// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
  EdgeNode *e;
  int i, k, gettop;
  int top = 0; // 用于栈指针下标索引
  int count = 0; // 用于统计输出顶点的个数
  int *stack; // 用于存储入度为0的顶点
  
  stack = (int *)malloc(GL->numVertexes * sizeof(int));
  
  for( i=0; i < GL->numVertexes; i++ )
  {
    if( 0 == GL->adjList[i].in )
    {
      stack[++top] = i; // 将度为0的顶点下标入栈
    }
  }
  
  // 初始化etv都为0
  top2 = 0;
  etv = (int *)malloc(GL->numVertexes*sizeof(int));
  for( i=0; i < GL->numVertexes; i++ )
  {
    etv[i] = 0;
  }
  stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
  
  while( 0 != top )
  {
    gettop = stack[top--]; // 出栈
    // printf("%d -> ", GL->adjList[gettop].data);
    stack2[++top2] = gettop; // 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
    count++;
    
    for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    {
      k = e->adjvex;
      // 注意要点！
      // 将k号顶点邻接点的入度-1，因为他的前驱：下边这个if条件是分析整个程序的已经消除
      // 接着判断-1后入度是否为0，如果为0则也入栈
      if( !(--GL->adjList[k].in) )
      {
        stack[++top] = k;
      }
      
      if( (etv[gettop]+e->weight) > etv[k] )
      {
        etv[k] = etv[gettop] + e->weight;
      }
    }
  }
  
  if( count < GL->numVertexes ) // 如果count小于顶点数，说明存在环
  {
    return ERROR;
  }
  else
  {
    return OK;
  }
}

// 求关键路径，GL为有向图，输出GL的各项关键活动
void CriticalPath(GraphAdjList GL)
{
  EdgeNode *e;
  int i, gettop, k, j;
  int ete, lte;
  
  // 调用改进后的拓扑排序，求出etv和stack2的值
  TopologicalSort(GL);
  
  // 初始化ltv都为汇点的时间
  ltv = (int *)malloc(GL->numVertexes*sizeof(int));
  for( i=0; i < GL->numVertexes; i++ )
  {
    ltv[i] = etv[GL->numVertexes-1];
  }
  
  // 从汇点倒过来逐个计算ltv
  while( 0 != top2 )
  {
    gettop = stack2[top2--]; // 注意，第一个出栈是汇点
    for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    {
      k = e->adjvex;
      if( (ltv[k] - e->weight) < ltv[gettop] )
      {
        ltv[gettop] = ltv[k] - e->weight;
      }
    }
  }
  
  // 通过etv和ltv求ete和lte
  for( j=0; j < GL->numVertexes; j++ )
  {
    for( e=GL->adjList[j].firstedge; e; e=e->next )
    {
      k = e->adjvex;
      ete = etv[j];
      lte = ltv[k] - e->weight;
      
      if( ete == lte )
      {
        printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
      }
    }
  }
}

时间复杂度分析

假设图中的顶点个数为，边的数目为。计算事件（顶点）的最早发生时间需要执行拓扑排序，时间复杂度为。计算事件的最晚发生时间需要根据顶点的最早发生时间进行逆向扫描（也就是从终点向汇点的方向）需要的时间复杂度。计算弧上活动的最早开始时间和最晚开始时间的时间复杂度为，所以总的求关键路径的时间复杂度为。

关键路径的应用

（1）完成整个工程至少需要多少时间；

（2）哪些活动是影响工程的关键。

1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。

说的更现实一点儿，以后大家如果要考PMP，那更是必须学会的算法了，有一天你成为了一个项目组组长，或者一个公司的老总，或者一个工程师，那么你就知道如何安排工程，知道什么是重点要关注的，知道如何进行资源配置。

向关键路径要时间，向非关键路径要资源

项目关键工作和关键路径的确定帮助项目经理抓住了项目工期管理中的主要矛盾，对于关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。

对不可控的任务，可采取办法规避安排在关键路径上面

关键路径要提前发现风险，前期采取必要的措施规避掉

关键路径是动态的，非关键路径有可能变成关键路径，所以项目过程中也要随时注意非关键路径的状况

总结

关键路径的查找过程中主要涉及四个概念，事件（顶点）的最早发生时间ETV，事件（顶点）的最晚发生时间LTV，活动（弧）的最早发生时间ETE，活动（弧）的最晚发生时间为LTE，其中事件的最早发生时间通过拓扑排序获得，而事件的最晚发生时间是通过逆向访问顶点（从源点到汇点的方向）结合最早发生时间获得，弧的活动的最早与最晚发生时间则是通过遍历一遍所有的弧结合事件的最早与最晚发生时间获得。关键路径在实际工程中应用广泛，如果你懂了，可以提高工程的工作效率，也可以适当地偷懒，哈哈，景禹就写到这里，这也是关于图的算法中的最后一个，希望小禹禹有所收获！

记得分享给周围的小伙伴奥，点个文末的在看，谢谢小禹禹，祝你们学习愉快，每天都进步。也感谢每一天看我文章的小禹禹，特别开心，当你们给我鼓励的时候，有时候你会觉得自己做这件事情的意义，但后来我才知道意义也许就在于让更多的小禹禹对每一个算法都深入理解，然后回馈给我的赞美，不过景禹马上硕士毕业答辩，之后更新文章的频率可能会略有降低，但我绝不放弃，因为小禹禹，谢谢你们！文章可能略微长了点儿，小禹禹多点儿耐心好好看，一定会有所收获的，你要想，景禹能花那么多时间给小禹禹写文章，我难道不能花一个小时认真彻底学会一个算法？答案是肯定的，我坚信关注并鼓励景禹的每一位小禹禹都会越来越优秀，一起加油！