C语言 关键路径（求解过程及算法实现） |
您所在的位置：网站首页 › aoe网代码 › C语言 关键路径（求解过程及算法实现） |
C语言 关键路径（求解过程及算法实现）
|
前言
在项目管理中，关键路径是一个非常重要的概念。通过计算关键路径可以确定项目最短完成时间，并对任务进行优先排序。同时，关键路径也能够帮助项目经理识别风险并采取相应的措施以确保项目能够按时完成。 一些基本概念 AOE-网：与AOV-网相对应的是AOE-网（Activity On Edge Netword），即以边表示活动的网。AOE-网是带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程完成的时间。下图为一个AOE-网： 在AOE-网中 源点：入度为0的节点，称作源点，也就是开始点。汇点：出度为0的节点，称作汇点，也就是完成点。带权路径长度：一条路径各弧上的权值之和称为该路径的带权路径长度（简称路径长度）。关键路径：从源点到汇点带权路径长度最长的路径，称作关键路径（Critical Path）。关键活动：关键路径上的活动叫做关键活动。 关键路径的求解 想要确定AOE-网中的关键路径先了解这几个定义： 事件的最早发生时间（Early Finish Time，EFT）：指在不影响整个项目完成的时间前提下，该事件所能发生的最早时间。对于AOE-网中的每个事件，只有其所有前继活动均完成后，该事件才能开始发生。因此，事件的最早发生时间就是从源点到该事件的最长路径长度，通常将源点事件的最早发生时间定义为0，可根据拓扑排序从源点到汇点递推。事件的最晚发生时间（Late Finish Time，LFT）：指在不影响整个项目完成的时间前提下，该事件所能发生的最晚时间，也就是该事件不能延误每一后继事件的最迟发生时间。源点事件和汇点事件的最晚发生时间等于其最早发生时间，而事件的最晚发生时间等于其后继事件的最晚发生时间减去该活动持续时间中最小的一个值，因此，我们可以根据逆拓扑顺序从汇点到源点递推。活动的最早开始时间（Early Start Time，EET）：每个活动的最早发生时间表示它可以开始的最早时间，这个时间由该活动的所有前驱活动中最晚结束时间决定的，因此，活动的最早开始时间等于弧尾（弧尾表示发出箭头的顶点， 弧头箭头指向的顶点）事件的最早发生时间。活动的最晚开始时间(Late Start Time，LET）：每个活动的最晚开始时间是指在不影响整个项目最晚完成时间的前提下，这个活动可以推迟到哪个时间开始，即能够满足不延误后面事件的最晚发生时间。所以活动的最晚开始时间等于弧头事件的最晚发生时间减去该活动的持续时间。时间余量（Slacktime）：时间余量是指每个活动可以延迟的时间，而不会延误整个项目的最早完成时间。时间余量等于活动最晚开始时间与最早开始时间之差。如果存在时间余量大于0，则活动的最晚开始时间可以延迟，而不会影响整个项目进度。若余量为0则称其为关键活动。 关键路径求解过程： 对图中顶点进行拓扑排序。根据拓扑序列递推求出每个事件的最早发生时间。根据逆拓扑序列通过汇点事件的最早发生时间递推求出每个事件的最晚发生时间。通过每个活动弧尾事件的最早发生时间求出活动的最早开始时间。通过每个活动弧头事件的最晚发生时间求出活动的最晚开始时间。求出各时间余量，找出关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径，关键路径可能不止一条。求解视频--> 关键路径讲解 关键路径算法实现由于每个事件的最早发生时间和最晚发生时间要按拓扑次序计算，所以关键路径算法的实现要基于拓扑排序算法，算法实现采用邻接表作为有向网的储存结构。 基本流程：1.定义一维数组ve[i]并置初值0（记录事件的最早发生时间）、一维数组vI[i]（记录事件的最晚发生时间）、一维数组topo[i]（记录拓扑序列的顶点序号）。 2.调用拓扑排序算法，使拓扑序列保存在topo中。 3.根据topo中的值，按从前向后的拓扑次序，依次求每个事件的最早发生时间，循环n（总顶点数）次，执行以下操作： 取得拓扑序列中的顶点序号k，k= topo[i];用指针p依次指向k的每个邻接顶点，取得每个邻接顶点的序号j，j=p->adjvex，依次更新顶点j的最早发生时间ve[j]（if(ve[i]weight) ve[i]= ve[k] + p->weight）；4.将每个事件的最迟发生时间vl[i]初始化为汇点的最早发生时间，即vl[i]=ve[n-1]。 5.根据topo中的值，按从后向前的逆拓扑次序，依次求每个事件的最迟发生时间，循环n次，执行以下操作： 取得拓扑序列中的顶点序号k，k= topo[i];用指针p依次指向k的每个邻接顶点，取得每个邻接顶点的序号j,j=p->adjvex,依次根据 k的邻接点,更新k的最迟发生时间vI[k]（if(vl[k]>vl[j]-p->weight) vl[k]=vl[j]-p->weight）；6.判断某一活动是否为关键活动，循环n次，执行以下操作： 对于每个顶点vi，用指针p依次指向vi的每个邻接顶点，取得每个邻接顶点的序号j,j=p->adjvex，分别计算活动的最早和最晚开始时间e和l;如果e和l相等，则活动为关键活动，输出弧。最后就可以根据关键活动得到关键路径啦。 #define _CRT_SECURE_NO_WARNINGS 1 #include #include #include #define MVNUM 100 typedef struct ArcNode { int adjvex; int weight; struct ArcNode* next; }ArcNode; typedef struct VNode { char data; ArcNode* firstarc; }VNode, AdjList[MVNUM]; typedef struct { AdjList vertices; int vexnum, arcnum; }ALGraph; //定位 int LocateVex(ALGraph* G, char v) { int i; for (i = 0; i < G->vexnum; i++) { if (G->vertices[i].data == v) { return i; } } return -1; } //有向网邻接表的建立 ALGraph* CreateGraph() { int i, j, k, v1, v2, w; ALGraph* G = malloc(sizeof(ALGraph)); printf("输入顶点数和边数:\n"); scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); printf("输入顶点信息：\n"); for (i = 0; i < G->vexnum; i++) { scanf("%c", &G->vertices[i].data); G->vertices[i].firstarc = NULL; } getchar(); for (k = 0; k < G->arcnum; k++) { printf("输入一条弧依附的起点和终点和权重：\n"); scanf("%c%c%d", &v1, &v2, &w); getchar(); i = LocateVex(G, v1), j = LocateVex(G, v2); ArcNode* p = malloc(sizeof(ArcNode)); p->adjvex = j; p->weight = w; p->next = G->vertices[i].firstarc; G->vertices[i].firstarc = p; } return G; } //--------------------------------------------------------------------------- //拓扑排序 bool TopoSort(ALGraph* G, int* topo) { int indegree[MVNUM] = { 0 };//记录顶点入度 int i, j, v; int count = 0;//记录输出的顶点数 int stack[MVNUM];//定义一个简单的栈 int top = 0;//栈顶指针 ArcNode* p = NULL; //统计各顶点入度 for (i = 0; i < G->vexnum; i++) { p = G->vertices[i].firstarc; while (p != NULL) { indegree[p->adjvex]++; p = p->next; } } //将所有入度为0的顶点入队 for (i = 0; i < G->vexnum; i++) { if (indegree[i] == 0) { stack[top++] = i; } } //栈非空时循环 while (top > 0) { v = stack[--top];//出栈一个顶点 topo[count++] = v;//排序的顶点数加1并将顶点存入数组topo //遍历该顶点为起点的所有边 p = G->vertices[v].firstarc; while (p != NULL) { indegree[p->adjvex]--;//入度减1 //若入度为0，入队 if (indegree[p->adjvex] == 0) { stack[top++] = p->adjvex; } p = p->next;//指向下一条边 } } //输出顶点数小于总顶点数，说明有环 if (count < G->vexnum) { printf("该图有环，拓扑排序失败。\n"); return false; } return true; } //---------------------------------------------------------------------------- //关键路径算法 bool CriticalPath(ALGraph* G) { int topo[MVNUM];//储存拓扑序列 int ve[MVNUM] = { 0 };//记录每个事件最早发生时间 int vl[MVNUM];//记录每个事件最晚发生时间 int i, j, k, e, l; ArcNode* p = NULL; if (!TopoSort(G, topo)) return false;//若拓扑排序失败，则存在有向环，返回false //按拓扑次序求每个事件的最早发生时间 for (i = 0; i < G->vexnum; i++) { k = topo[i];//取拓扑序列中的顶点序号k p = G->vertices[k].firstarc;//指针p指向顶点k的第一个邻接点 //更新顶点k的所以邻接点的最早发生时间 while (p != NULL) { j = p->adjvex;//j为顶点k的邻接点的序号 //更新顶点j最早发生时间（不理解的话，找个AOE-网代入联想下） if (ve[j] < ve[k] + p->weight) { ve[j] = ve[k] + p->weight; } p = p->next;//指针噗指向下一邻接点 } } //初始化数组Vl for (i = 0; i < G->vexnum; i++) { vl[i] = ve[G->vexnum - 1]; } //按逆拓扑次序求每个事件的最晚发生时间 for (i = G->vexnum - 1; i >= 0; i--) { k = topo[i];//取拓扑序列中的顶点序号k p = G->vertices[k].firstarc;//指针噗指向顶点k的第一个邻接点 //根据顶点k的邻接点更新k的最晚发生时间 while (p != NULL) { j = p->adjvex;//j为邻接点序号 //更新顶点k的最晚发生时间 if (vl[k] > vl[j] - p->weight) { vl[k] = vl[j] - p->weight; } p = p->next;//指针p指向下一邻接点 } } //判断每一活动是否为关键活动 //每次循环针对以顶点i为开始点关联的所有活动 for (i = 0; i < G->vexnum; i++) { p = G->vertices[i].firstarc;//指针p指向顶点i的第一个邻接点 while (p != NULL) { j = p->adjvex;//j为邻接点序号 e = ve[i];//计算活动的最早开始时间 l = vl[j] - p->weight;//计算活动的最晚开始时间 //若为关键活动，则输出 if (e == l) { printf(" ", G->vertices[i].data, G->vertices[j].data); } p = p->next;//指针p指向下一邻接点 } } } int main() { ALGraph* G = CreateGraph(); printf("关键活动为：\n"); CriticalPath(G); return 0; } 运行程序求下图的关键路径：
运行结果如下：
关键路径算法是一个解决项目管理中最短时间问题的经典工具。在计算关键路径时，我们需要对整个项目进行遍历，并计算出每个活动的最早开始时间、最晚开始时间、最早完成时间以及最晚完成时间，进而得到整个项目的关键路径。因此，关键路径算法的时间复杂度相对较高，但也有一些优化方法可以应用。 算法的时间复杂度分析：对于有 n 个顶点和 e 条弧的 AOE 网而言，拓扑排序的时间复杂度是 O(n+e)，计算事件的最晚发生时间的时间复杂度也是 O(n+e)，最后计算关键路径的时间复杂度还是 O(n+e)，所以整体的时间复杂度依然是 O(n+e)。
|
【本文地址】
今日新闻 |
推荐新闻 |