关键路径问题也是从实际中抽象出来的,他解决的是这么一类的问题:加入我们完成一件事需要6个工序,其中的一些该工序是可以并行进行的,另一些工序的顺序是有一定要求的,并且每道工序花费的时间并不一定相同。比如做完A才能做B或者C,花费的时间分别为3,2.做完B之后才能做E,花费的时间为3。做完C之后才能做F,花费的时间为3。B和C都做完才能做D,花费的时间分别为:2,4.C,D,E都做完之后才能做最后一件事F,花费的时间分别为:3,2,1。
假如我想提高整个事情的速度,那么我应该缩短哪些步骤的时间呢?这是一个值得思考的问题,因为假如我缩短了AB之间的时间,那么有可能会出现这么一种情况:虽然AB的时间提前了,进而BE的时间提前了,导致EF的时间提前了;但是由于AC的时间没有发生变化,导致C,D都不能尽早完成,所以虽然E已经很早完成了,但是还得等C、D完成,才能一起做F。形象的说,所谓的关键路径,就是对整个工程进度缩短有重要影响的路径。
那么如何求关键路径呢?整个过程稍微有点复杂:从起始点A开始,先计算A到其他节点的最长路径,这个路径成为这个节点的最早发生时间。因为只有他前面的事全都做完,他才能开始。然后从最后一个节点回退,计算回退到这个节点的最短路径,这个时间成为最晚开始时间。因为它表明了再不推迟整个工期的前提下,这个活动最晚必须的时间。对于中间的每个节点,都会有一个最晚开始键-最早开始时间的余量。而那些余量等于0的节点,就是那些他做完就可以做下一件事的节点,就是关键节点,而沿着关键节点上的路径,就称为关键路径。而其他的节点,因为有余量的存在,所以早一点或者晚一点,对于整个工程的进度影响不大。
这个问题用程序怎么表示呢?其实,这就是一个AOE网(activity on edge),即边表示活动。就是一个带权的有向无环图。权的大小表示花费的时间。我还设置了int* early;表示最早完成时间,int* late;表示最迟开始时间;以及访问标记bool* find;。
#include <stdio.h> #include <malloc.h> #include <limits.h> typedef int** ADJACENTMTRIX; typedef struct activityOnEdge { ADJACENTMTRIX matrix; int vertexNumber; int arcNumber; char* vertex; //最早完成时间 int* early; //最迟开始时间 int* late; //标记 bool* find; }AOE; AOE initgraph(int ); void destroyAOE(AOE* ); bool addArc(AOE* ,char ,char ,int ); bool deleteArc(AOE* ,char ,char ); void printGraph(AOE* ); //关键路径相关函数 //计算目标节点的最早开始时间 int calculateMax(AOE* g,int target,int n); //计算目标节点的最迟开始时间 int calculateMin(AOE* g,int target,int n); //找到这个节点的后面的节点 int findNextNodes(int ,AOE* ); //找到这个节点前面的节点 int findPreNodes(int ,AOE* ); //计算每个节点的最早发生时间 void calculateEarliestStartTime(AOE* ); //计算每个节点的最迟开始时间 void calculateLatestStartTime(AOE* ); void keyPath(AOE* );
先看寻找最短路径的函数:
//输出的是一条关键路径 void keyPath(AOE* g) { //计算每个节点的最早发生时间 calculateEarliestStartTime(g); //测试打印: // printf("最早开始时间依次为:"); // for(int i = 0; i < g->vertexNumber;++i) // printf("%d ",g->early[i]); // printf("\n"); //计算每个节点的最晚开始时间 calculateLatestStartTime(g); // printf("最迟开始时间依次为:"); // for(int i = 0; i < g->vertexNumber;++i) // printf("%d ",g->late[i]); // printf("\n"); printf("关键路径为:"); for(int i = 0; i < g->vertexNumber;++i) { if(g->early[i] == g->late[i] ) printf("%c ",g->vertex[i]); } }
其实就是上面描述的3步:找到每个节点的最早开始时间、最迟开始时间,然后判断其中相等的是哪些节点。计算每个节点的最早发生时间则由下面的函数完成:
void calculateEarliestStartTime(AOE* g) { //从起始节点的下一个开始 for(int i = 1; i < g->vertexNumber;++i) { //找到这个节点前驱 int cnt = findPreNodes(i,g); //找出对应的最小值 g->early[i] = calculateMax(g,i,cnt); } }
它所完成的工作是这样的:对于每个节点,先找到这个节点的前驱,然后再计算其中的最早开始时间。这个两个函数如下:
//找到指向这个节点的节点,并用find数组中的true来标记,返回前驱的个数 int findPreNodes(int i,AOE* g) { //先把find数组清空 for(int j = 0; j < g->vertexNumber;++j) g->find[j] = false; int cnt= 0; for(int j = 0; j < g->vertexNumber;++j) { if(INT_MAX != g->matrix[j][i]) { //给find做标记 g->find[j] =true; ++cnt; } } return cnt; } int calculateMax(AOE* g,int target,int n) { int* tmp = (int*)malloc(sizeof(int) * n); int max = 0; int cnt = 0; //遍历所有节点 for(int i = 0; i < g->vertexNumber;++i) { //如果这个节点指向目标节点 if(true == g->find[i]) { tmp[cnt] = g->matrix[i][target] + g->early[i]; ++cnt; } } for(int i = 0; i < cnt;++i) { if(tmp[i] > max) max = tmp[i]; } free(tmp); return max; }
同理,计算最晚开始时间使用下面的一些函数完成的:
//计算每个节点的最迟开始时间 void calculateLatestStartTime(AOE* g) { //每个节点的最迟开始时间初始化为最后一个节点的最早开始时间 for(int i = 0; i < g->vertexNumber;++i) { g->late[i] = g->early[g->vertexNumber-1]; } //从最后倒数第二个节点开始,回溯前面的节点 for(int i = g->vertexNumber-2;i >= 0;--i) { //找到这个节点的后继 int cnt = findNextNodes(i,g); g->late[i] = calculateMin(g,i,cnt); } } //找到这个节点的后继,并用find数组中的true来标记,返回后继的个数 int findNextNodes(int i,AOE* g) { //先把find数组清空 for(int j = 0; j < g->vertexNumber;++j) g->find[j] = false; int cnt= 0; for(int j = 0; j < g->vertexNumber;++j) { if(INT_MAX != g->matrix[i][j]) { //给find做标记 g->find[j] =true; ++cnt; } } return cnt; } //计算其中的最小值 int calculateMin(AOE* g,int target,int n) { //存储所有指向目标节点的节点的距离 int* tmp = (int*)malloc(sizeof(int) * n); int min = INT_MAX; int cnt = 0; //遍历所有节点 for(int i = 0; i < g->vertexNumber;++i) { //如果这个节点指向目标节点 if(true == g->find[i]) { //这个节点的后继节点的最迟开始时间 - 这个节点到后继节点的时间 tmp[cnt] = g->late[i] - g->matrix[target][i]; ++cnt; } } //对tmp中的所有最早完成时间求最小值 for(int i = 0; i < cnt;++i) if(tmp[i] < min) min = tmp[i]; free(tmp); return min; }
程序就是这么多了,只需要在主程序中定义一个图,然后添加边组成AOE网,然后调用keyPath函数就可以。