写在前面:博主是普通的19届非软工学生，平时最大的爱好是听歌、逛b站。 博主喜欢的语言可以开花、开花、开花、开花。 (博主的理解是第一个人。 所以，要做自己想做的、不后悔、不后悔、认为有意义的事，不要浪费这个美好的青春时代。 博主的目的是记录所学内容，便于自己复习。 一边记录知识，一边获得部分阅读数，得到更多人的认可，满足小小的成就感，同时在写博客的路上交到更多志同道合的朋友，在技术道路上不再孤单。
目录：
1.AOE网
2 .关键路径
3 .寻求关键路径的具体实现
4 .关键路径c语言的完整代码实现
5 .关键路径总结
1.AOE网AOE网基于AOV网，每边各有权重，有向无环网。 在这里，权重表示活动的持续时间。
上图为AOE网络。 例如，a1=6表示完成a1活动需要6天。 AOE网的各顶点表示其前一个活动已经完成，可以开始后一个活动。 例如，V5表示a4和a5活动已完成，a7和a8可以开始。
使用AOE网络时，如果将AOE网络视为整个项目，则完成整个项目至少需要多长时间？
解决这个问题的关键是找出从AOE网络点到终点长度最长的路径，确保在所有活动结束之前完成。
起点是点为0的点，称为“源点”； 终点是出度为0的点，称为“汇点”。 这条最长的路径被称为“关键路径”。
2 .关键路径为了求出被给定的AOE网络的关键路径，需要知道以下4个统计数据。
在AOE网络的顶点，有最早的发生时刻(用ve ) j表示)和最晚的发生时刻(用VL ) j表示)两个时间。 边缘也具有两个时间：最早开始时间(由e ) I表示)和最晚开始时间(由l ) I表示)。 统计数据表示意义ve(j )。 最早的发生时间为对于 AOE 网中的任意一个顶点来说，从源点到该点的最长路径代表着该顶点的最早发生时间，通常用 Ve(j)表示。，例如，下图中从V1到V5有两条路径。 V1作为源点开始后，a1和a2同时开始活动，但由于a1和a2活动的时间长度不同，最终V1-V3-V5的路径会先完成。 但是，V5以后的活动并不是可以开始的，V1-V2-V5这一路径也需要在完成之后开始。 因此，对于V5来说，ve(5)=7。 VL(j ) :最迟发生时间表示在不推迟整个工期的前提下，事件 Vk 允许的最晚发生时间。例如，在下图中，在得知全工期的完成时间为18天的基础上，V7最迟在第16天的时间点开始。 由于a10事件至少需要两天才能完成，因此V7事件延迟将延迟整个工期。 因此，对V7来说，其VL(7)=16。 e(I ) :最早的开始时间表示活动 ai 的最早开始时间，如果活动 ai 是由弧 Vk,Vj 表示的，那么活动 ai 的最早开始的时间就等于时间 Vk 的最早发生时间，也就是说：e[i] = ve[k]。e(i )可以很好地理解。 用图1的a4来说，如果a4要开始活动，首先前提是V2事件开始。 所以e[4]=ve[2]。 L(I ) :最迟开始时间表示活动 ai 的最晚开始时间，如果活动 ai 是由弧 Vk,Vj 表示，ai 的最晚开始时间的设定要保证 Vj 的最晚发生时间不拖后。所以，l[i]=Vl[j]-lenVk,Vj。
了解以上四种类型的统计数据后，可以直接查找AOE网关键路径上的所有关键活动。 方法包括：对于所有的边来说，如果它的最早开始时间等于最晚开始时间，称这条边所代表的活动为关键活动。由关键活动构成的路径为关键路径。
3 .寻求关键路径的具体实现，还是用以下例子
关键路径首先要求完成ve(j )、ve(j )、e )、l (I )四种统计信息的准备。
1.ve(j )要求从源到各顶点的最长路径长度为(最大长度)。
2.VL(j )求出各顶点最迟发生时间(从后向前按，往往选择最小的) :
3.e(I )求出各边的ai活动的最早开始时间：
4.L(I )在各边中求出ai活动的最慢开始时间(往往选择最小的) )。
比较L(I )和L(I )，其中a1、a4、a7、a8、a10、a11的值分别相同，因此图1的AOE网有两个关键路径。
4 .关键路径c语言完整代码实现# include stdio.h # include stdlib.h # definemax _ vertex _ num 20//最大顶点数#
define VertexType int//顶点数据的类型typedef enum{false,true} bool;//建立全局变量，保存边的最早开始时间VertexType ve[MAX_VERTEX_NUM];//建立全局变量，保存边的最晚开始时间VertexType vl[MAX_VERTEX_NUM];typedef struct ArcNode{ int adjvex;//邻接点在数组中的位置下标 struct ArcNode * nextarc;//指向下一个邻接点的指针 VertexType dut;}ArcNode;typedef struct VNode{ VertexType data;//顶点的数据域 ArcNode * firstarc;//指向邻接点的指针}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组typedef struct { AdjList vertices;//图中顶点及各邻接点数组 int vexnum,arcnum;//记录图中顶点数和边或弧数}ALGraph;//找到顶点对应在邻接表数组中的位置下标int LocateVex(ALGraph G,VertexType u){ for (int i=0; i<G.vexnum; i++) { if (G.vertices[i].data==u) { return i; } } return -1;}//创建AOE网，构建邻接表void CreateAOE(ALGraph **G){ *G=(ALGraph*)malloc(sizeof(ALGraph)); scanf("%d,%d",&((*G)->vexnum),&((*G)->arcnum)); for (int i=0; i<(*G)->vexnum; i++) { scanf("%d",&((*G)->vertices[i].data)); (*G)->vertices[i].firstarc=NULL; } VertexType initial,end,dut; for (int i=0; i<(*G)->arcnum; i++) { scanf("%d,%d,%d",&initial,&end,&dut); ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=LocateVex(*(*G), end); p->nextarc=NULL; p->dut=dut; int locate=LocateVex(*(*G), initial); p->nextarc=(*G)->vertices[locate].firstarc; (*G)->vertices[locate].firstarc=p; }}//结构体定义栈结构typedef struct stack{ VertexType data; struct stack * next;}stack;stack *T;//初始化栈结构void initStack(stack* *S){ (*S)=(stack*)malloc(sizeof(stack)); (*S)->next=NULL;}//判断栈是否为空bool StackEmpty(stack S){ if (S.next==NULL) { return true; } return false;}//进栈，以头插法将新结点插入到链表中void push(stack *S,VertexType u){ stack *p=(stack*)malloc(sizeof(stack)); p->data=u; p->next=NULL; p->next=S->next; S->next=p;}//弹栈函数，删除链表首元结点的同时，释放该空间，并将该结点中的数据域通过地址传值给变量i;void pop(stack *S,VertexType *i){ stack *p=S->next; *i=p->data; S->next=S->next->next; free(p);}//统计各顶点的入度void FindInDegree(ALGraph G,int indegree[]){ //初始化数组，默认初始值全部为0 for (int i=0; i<G.vexnum; i++) { indegree[i]=0; } //遍历邻接表，根据各链表中结点的数据域存储的各顶点位置下标，在indegree数组相应位置+1 for (int i=0; i<G.vexnum; i++) { ArcNode *p=G.vertices[i].firstarc; while (p) { indegree[p->adjvex]++; p=p->nextarc; } }}bool TopologicalOrder(ALGraph G){ int indegree[G.vexnum];//创建记录各顶点入度的数组 FindInDegree(G,indegree);//统计各顶点的入度 //建立栈结构，程序中使用的是链表 stack *S; //初始化栈 initStack(&S); for (int i=0; i<G.vexnum; i++) { ve[i]=0; } //查找度为0的顶点，作为起始点 for (int i=0; i<G.vexnum; i++) { if (!indegree[i]) { push(S, i); } } int count=0; //栈为空为结束标志 while (!StackEmpty(*S)) { int index; //弹栈，并记录栈中保存的顶点所在邻接表数组中的位置 pop(S,&index); //压栈，为求各边的最晚开始时间做准备 push(T, index); ++count; //依次查找跟该顶点相链接的顶点，如果初始入度为1，当删除前一个顶点后，该顶点入度为0 for (ArcNode *p=G.vertices[index].firstarc; p ; p=p->nextarc) { VertexType k=p->adjvex; if (!(--indegree[k])) { //顶点入度为0，入栈 push(S, k); } //如果边的源点的最长路径长度加上边的权值比汇点的最长路径长度还长，就覆盖ve数组中对应位置的值，最终结束时，ve数组中存储的就是各顶点的最长路径长度。 if (ve[index]+p->dut>ve[k]) { ve[k]=ve[index]+p->dut; } } } //如果count值小于顶点数量，表明有向图有环 if (count<G.vexnum) { printf("该图有回路"); return false; } return true;}//求各顶点的最晚发生时间并计算出各边的最早和最晚开始时间void CriticalPath(ALGraph G){ if (!TopologicalOrder(G)) { return ; } for (int i=0 ; i<G.vexnum ; i++) { vl[i]=ve[G.vexnum-1]; } int j,k; while (!StackEmpty(*T)) { pop(T, &j); for (ArcNode* p=G.vertices[j].firstarc ; p ; p=p->nextarc) { k=p->adjvex; //构建Vl数组，在初始化时，Vl数组中每个单元都是18，如果每个边的汇点-边的权值比源点值小，就保存更小的。 if (vl[k]-p->dut<vl[j]) { vl[j] = vl[k]-p->dut; } } } for (j = 0; j < G.vexnum; j++) { for (ArcNode*p = G.vertices[j].firstarc; p ;p = p->nextarc) { k = p->adjvex; //求各边的最早开始时间e[i],等于ve数组中相应源点存储的值 int ee = ve[j]; //求各边的最晚开始时间l[i]，等于汇点在vl数组中存储的值减改边的权值 int el = vl[k]-p->dut; //判断e[i]和l[i]是否相等，如果相等，该边就是关键活动，相应的用*标记；反之，边后边没标记 char tag = (ee==el)?'*':' '; printf("%3d%3d%3d%3d%3d%2cn",j,k,p->dut,ee,el,tag); } }}int main(){ ALGraph *G; CreateAOE(&G);//创建AOE网 initStack(&T); TopologicalOrder(*G); CriticalPath(*G); return 0;} 5.关键路径小结在求关键路径的算法中，在求每一个事件的最早最迟发生时间，以及活动得到最早和最迟开始时，都要对所有顶点及每一个顶点边表中的边结点进行检查，因此求关键路径的时间复杂度为O(n+e)
本篇博客转载C语言中文网