在学习了拓扑排序之后，我们可以开始学习关键路径了。拓扑排序可以有多个起点和多个终点，跟拓扑排序不同的是，关键路径只能有一个起点、一个终点。

我们发现，这一条关键路径一定是一个拓扑排序的子序列。所以我们就可以用拓扑排序计算关键路径了。但问题是拓扑排序有多种结果，怎么才能拿到关键路径 (权重的和最大) 呢？

怎么计算每个节点的earlyTime呢？我们可以用递推。
例如：从起点开始，有两条路径可以到达3号点。分别是：8 -> 0 -> 3和8 -> 2 -> 3。我们只需要取这两条路径的权重最大值，那就是8 -> 3的权重。递推关系式：
earlyTime(0) = max[earlyTime(0), earlyTime(8) + weight8_0]
earlyTime(2) = max[earlyTime(2), earlyTime(8) + weight8_2]

earlyTime(3) 需要计算两次：
earlyTime(3) = max[earlyTime(3), earlyTime(0) + weight0_3]
earlyTime(3) = max[earlyTime(3), earlyTime(2) + weight2_3]

用同样的方法就可以计算出终点7的earlyTime，也就是从起点到终点的最大权重和。

在得到从起点到终点的最大权重和之后，我们就可以反向计算了。显然，终点的lastTime 和earlyTime是同一个值。那么其它结点的lastTime的初始值是多少呢？可以简单的赋值为∞ (无穷大，inf)，或者也同样设置为终点的lastTime。

计算结点的lastTime与计算earlyTime类似，也可以用递推。例如一共有两条路径从终点出发，反向走到结点4，分别是7 -> 5 -> 4和7 -> 6 -> 4。递推关系式：
lastTime(5) = min[lastTime(5), lastTime(7) - weight5_7]
lastTime(6) = min[lastTime(6), lastTime(7) - weight6_7]

lastTime(4) 需要计算两次：
lastTime(4) = min[lastTime(4), lastTime(5) - weight4_5]
lastTime(4) = min[lastTime(4), lastTime(6) - weight4_6]
用同样的方法就可以计算出所有结点的lastTime。接着对比一下每个结点的earlyTime和lastTime。如果这两个值相等，则这个结点一定是关键路径上的结点，输出这个结点的编号即可。

总体的代码如下：

#include <stdio.h> #include <stdlib.h> int arr[9][9]; //存放weight的二维数组 int size = 9; //图上的结点数 int inf = 999; //无穷大 //声明结构体:结点  struct Node{ 
    int index; //编号  int inDegree; //入度  int earlyTime = 0; //最早的发生时间，默认为0  int lastTime = inf; //最晚的发生时间，默认为无穷大  struct Node * next; //下一个结点的指针  }; int stack [100]; //用栈辅助实现拓扑排序，用数组实现栈 int top = 0; //栈的头素的index  int queue[100]; //一个用数组实现的队列  int head = 0; //队列的头  int tail = 0; //队列的尾  //用一个数组存放首素。每个首素后面用指针连接各个结点  struct Node arrNode[8]; //头插法，得到的结果的次序是反的是得到的结果的次序是反的  void addNode(int parentIndex, int nodeIndex) { 
    struct Node * parentNode; parentNode = &arrNode[parentIndex]; //向操作系统申请空间  struct Node *temp = (struct Node *)(malloc(sizeof(struct Node))); temp->index = nodeIndex; temp->next = parentNode->next; parentNode->next = temp; arrNode[nodeIndex].inDegree++; //入度 + 1 temp->inDegree = arrNode[nodeIndex].inDegree; } //遍历一个结点，和它的所有相连的结点  void traverse(int parentIndex) { 
    struct Node * node = &arrNode[parentIndex]; while(node != NULL) { 
    printf("%d (%d) --> ", node->index, node->inDegree); node = node->next; } printf("\r\n"); } int max(int a, int b) //求两个数中的最大值  { 
    return a > b ? a : b; //三运算符 } int min(int a, int b) //求两个数中的最小值 { 
    return a < b ? a : b; //三运算符 } //用二维数组储存图，其实要的仅仅是weight  void initMap() { 
    for(int i = 0; i < size; i++) { 
    for(int j = 0; j < size; j++) { 
    arr[i][j] = 0; } } //对有向图中的边进行赋值 arr[0][1] = 10; arr[0][3] = 2; arr[1][4] = 3; arr[2][3] = 3; arr[3][4] = 4; arr[4][5] = 6; arr[4][6] = 3; arr[5][7] = 2; arr[6][7] = 3; arr[8][0] = 3; arr[8][2] = 3; } int TopologicalOrderByStack() //栈辅助实现的拓扑排序  { 
    int count = 0; //用来计数 int index = 0; //输出的结点的编号  int i = 0; //循环变量  //1、遍历所有结点，寻找入度为0的结点，并把编号存放在stack中  for(i = 0; i < size; i++) { 
    struct Node node = arrNode[i]; if(node.inDegree == 0) { 
    stack[top] = i; //把结点的编号存放到stack中  top++; //top + 1  } } //2、弹出栈中的结点，输出结点编号。同时让该结点的下一级结点的入度-1  //3、循环，直到栈中的结点为0，即top == 0  while(top > 0) { 
    top--; //top的位置没有内容，所以要先 - 1  index = stack[top]; //得到存放在stack中的编号  queue[tail] = index; //把编号存放到queue中  tail++; //存放数据后，队列的tail + 1  printf("%d(%d) -> ", index, arrNode[index].earlyTime); //输出编号和earlyTime count++; //计数 + 1  //从arrNode中获得结点的指针  struct Node * parentNode = &arrNode[index]; //得到数组arrNode中的指定节点  struct Node * node = parentNode->next; //得到arrNode中的指定节点的子节点 //遍历 while(node != NULL) //如果子节点不是NULL就循环  { 
    int sonIndex = node->index; //子节点的index  //计算子节点的earlyTime arrNode[sonIndex].earlyTime = max(arrNode[sonIndex].earlyTime, arrNode[index].earlyTime + arr[index][sonIndex]); //从arrNode中获得结点、结点信息  if(arrNode[sonIndex].inDegree > 0) //子节点的入度 > 0  { 
    //结点的inDegree - 1  arrNode[sonIndex].inDegree--; //如果结点的inDegree == 0 if(arrNode[sonIndex].inDegree == 0) { 
    //把结点的index (也就是sonIndex) 加入到stack中  stack[top] = sonIndex; top++; } } node = node->next; //指针指向下一个子节点  } } if(count < size) //如果输出的结点数 < 总结点数  { 
    return 0; //不存在拓扑排序 } return 1; //存在拓扑排序  } void releaseResource() //释放资源 { 
    //同前 } void showQueue() { 
    printf("\r\n显示队列：\r\n"); int myHead = head; while(myHead < tail) { 
    printf("%d, ", queue[myHead]); myHead++; } printf("\r\n\r\n"); } void getKeyRoute() //关键路径  { 
    //最终结点的最晚发生时间就是它的最早发生时间 arrNode[queue[tail - 1]].lastTime = arrNode[queue[tail - 1]].earlyTime; //从终点往起点开始，反着计算。这种计算方式的时间复杂度为O(N^2)  for(int i = tail - 1; i >= head; i--) { 
    for(int j = i; j >= head; j--) { 
    if(arr[queue[j]][queue[i]] > 0) { 
    //注意，这是一个有向图。所以不能用arr[queue[i]][queue[j]]， //arr[queue[i]][queue[j]]的值一定是0，用arr[queue[j]][queue[i]]  arrNode[queue[j]].lastTime = min(arrNode[queue[j]].lastTime, arrNode[queue[i]].lastTime - arr[queue[j]][queue[i]]); //显示每个节点的lastTime  //printf("arrNode[%d].lastTime = %d, arr[queue[j]][queue[i]] = %d\r\n", queue[j], arrNode[queue[j]].lastTime, arr[queue[j]][queue[i]]); } } } printf("\r\n\r\n显示每个节点和它的lastTime：\r\n"); for(int i = 0; i < size; i++) { 
    printf("%d (%d), ", queue[i], arrNode[queue[i]].lastTime); } printf("\r\n\r\n关键路径：\r\n"); for(int i = 0; i < size; i++) { 
    //如果结点的earlyTime与反向计算得到的lastTime相等，说明是关键路径上的点 //但是，如果有多条关键路径，这里只会傻傻的一起输出，而不是分开输出。  if(arrNode[queue[i]].earlyTime == arrNode[queue[i]].lastTime) { 
    printf("%d(%d), ", queue[i], arrNode[queue[i]].lastTime); } } } int main() { 
    initMap(); //初始化地图 (weight) //初始化  for(int i = 0; i < size; i++) { 
    arrNode[i].index = i; arrNode[i].inDegree = 0; arrNode[i].next = NULL; } //插入数据 addNode(0, 1); addNode(0, 3); addNode(1, 4); addNode(2, 3); addNode(3, 4);addNode(4, 5); addNode(4, 6); addNode(5, 7); addNode(6, 7); addNode(8, 0);addNode(8, 2); //addNode(5, 1); //加上这一行，就会形成环，也就没有拓扑排序了  for(int i = 0; i < size; i++) //对每个节点遍历它的相邻节点 { 
    traverse(i); } if(TopologicalOrderByStack()) { 
    printf("存在拓扑排序\r\n"); } else { 
    printf("不存在拓扑排序\r\n"); } ///完成拓扑排序和计算earlyTime  showQueue(); //显示队列中的内容，这里把队列当初数组看  printf("拓扑排序的首素：%d\r\n", queue[head]); printf("拓扑排序的尾素：%d\r\n", queue[tail - 1]); getKeyRoute(); //计算关键路径  releaseResource(); //释放资源  printf("\r\nHello\r\n"); return 0; } 

运行结果如下：

很明显，关键路径上的结点的earlyTime与lastTime都相等。如果一个有向图中有多条关键路径，这个代码不会分别显示。只会把所有结点按照拓扑排序中的次序依次显示。
这个算法的思路不难，但是过程却比较复杂，代码也相对比较长。代码中大部分是拓扑排序的内容，真正计算关键路径的代码其实不多。另外，这里使用邻接矩阵的方式储存图的边长 (weight)，需要两层for循环才能最终确定每一个结点的lastTime，所以关键路径算法的时间复杂度为O(N^2)。

关键路径算法是“图”的最后一个扩展算法。它是运筹学的一部分。根据关键路径，可以明确加快哪些步骤可以加速整个工程的进度。