求AOE网络中的关键路径算法

F福建电脑UJIAN COMPUTER福建电脑2017年第11期1引言有向无环图在工程和管理中的应用有两种：AOV 网和AOE 网，前者用顶点表示活动，有向弧表示活动间。

后者用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间。

AOE 网在工程计划和管理中用于解决两类问题，一类是求解影响工程进度的关键活动，另一类是求解完成整个工程所需要的最少时间。

在AOE 网中唯一一个入度为零的顶点称作源点；唯一一个出度为零的顶点称作汇点。

从源点到汇点的最长路径称作关键路径，关键路径的长度就是完成整个工程任务所需要的最短时间。

关键路径上的活动都是关键活动。

如果这些活动中的任意一项未能按期完成，则整个工程就要延期。

如果某个关键活动的进度能够提前，那么整个工程就可能提前完成。

2算法所用数据结构：设图G =（V ，VR ）是一个具有n 个顶点的有向网，其中，V 为顶点集，VR 为两个顶点间的关系的集合。

G 的邻接矩阵定义为如下n 伊n 矩阵A ：则定义如下数组和矩阵：top_sort ［n ］：存放G 的一个拓扑序列ve ［n ］：ve ［i ］为事件vi 的最早发生时间vl ［i ］：vl ［i ］为事件vi 的最晚发生时间e ［n ］［n ］：e ［i ］［j ］为活动<vi ，vj>的最早开始时间l ［n ］［n ］：l ［i ］［j ］为活动<vi ，vj>的最晚开始时间3基于邻接矩阵的拓扑排序(Topological Sort)的实现在顶点集V 和弧集E 构成的有向图G=(V ，E)中，满足如下条件的顶点序列(v i1，v i2，v i3…，v in )称为拓扑序列：对于序列中的任意两个顶点v i 、v j ，如果在G 中存在一条从v i 到v j 的路径，那么在序列中v i 一定在v j 之前。

如图1所示有向网的一个拓扑序列为：v 0，v 1，v 2，v 3，v 4，v 5，v 6，v 7，v 8。

数据结构课程设计报告专业网络工程班级姓名学号指导老师评分计算AOE网的关键路径AOE网即边表示活动的网络。

通常，可用AOE网来估算工程计划的完成时间。

如下所示的AOE网包括11项活动，9个事件，每个事件都有所需的完成时间。

我们现在要解决的是：（1）完成整项工程至少需要多少时间（最短时间）；（2）哪些活动是影响工程进度的关键（关键活动）。

用e(i)表示活动最早开始时间，l(i)表示活动的最迟开始时间，则l(i)-e(i)为完成该活动的时间余量。

对于本例列表如下：下图就是上述AOE网的关键路径：请编程完成下列工作：1、输入：（1）顶点的信息和入度；（2）AOE网的边（始点、终点和权值）。

2、输出：（1） AOE网的邻接表（按“顶点入度：—>顶点权值”的格式输出）如a 0：-->4 5-->3 4-->2 6（2）输出关键活动每行所显示的分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量：当l(i)-e(i)=0时，在该行注明为关键活动。

如：a b 0 0 0 关键活动源程序#include<stdio.h>#include<stdlib.h>#include<iomanip.h>#include <process.h>//#define PROJECTNUMBER 9//10//#define PLANNUMBER 11//13typedef struct node{int adjvex;int dut;struct node *next;}edgenode;typedef struct{int projectname;int id;edgenode *link;}vexnode;//vexnode Graphicmap[PROJECTNUMBER];void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber){int begin,end,duttem;edgenode *p;for(int i=0;i<projectnumber;i++){Graphicmap[i].projectname=i;Graphicmap[i].id =0;Graphicmap[i].link =NULL;}printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n");printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n"); for(int k=0;k<activenumber;k++){scanf("%d,%d,%d",&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode));p->adjvex =end-1;p->dut =duttem;Graphicmap[end-1].id ++;p->next =Graphicmap[begin-1].link ;Graphicmap[begin-1].link =p;}}int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime){int i,j,k,m=0;int front=-1,rear=-1;int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间 int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间edgenode *p;totaltime=0;for(i=0;i<projectnumber;i++) ve[i]=0;for(i=0;i<projectnumber;i++){if(Graphicmap[i].id==0){topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link ;while(p){k=p->adjvex ;Graphicmap[k].id --;if(ve[j]+p->dut >ve[k])ve[k]=ve[j]+p->dut ;if(Graphicmap[k].id ==0)topologystack[++rear]=k;p=p->next ;}}if(m<projectnumber){printf("\n本程序所建立的图有回路不可计算出关键路径\n");printf("将退出本程序\n");return 0;}totaltime=ve[projectnumber-1];for(i=0;i<projectnumber;i++)vl[i]=totaltime;for(i=projectnumber-2;i>=0;i--){j=topologystack[i];p=Graphicmap[j].link ;while(p){k=p->adjvex ;if((vl[k]-p->dut )<vl[j])vl[j]=vl[k]-p->dut ;p=p->next ;}}i=0;printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |\n");for(j=0;j<projectnumber;j++){p=Graphicmap[j].link;while(p){k=p->adjvex ;e[++i]=ve[j];l[i]=vl[k]-p->dut;printf("| %4d | %4d | %4d | %4d | %4d |",Graphic map[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf(" 关键活动 |");printf("\n");p=p->next ;}}return 1;}void seekkeyroot(){int projectnumber,activenumber,totaltime=0;system("cls");printf("请输入这个工程的化成图形的节点数:");scanf("%d",&projectnumber);printf("请输入这个工程的活动个数:");scanf("%d",&activenumber);vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode)); CreateGraphic(Graphicmap,projectnumber,activenumber);SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime);system("pause");}int main(){char ch;for(;;){do{system("cls");printf("| 欢迎进入求关键路径算法程序 |");for(int i=0;i<80;i++)printf("*");printf("%s","(S)tart开始输入工程的节点数据并求出关键路径\n"); printf("%s","(E)xit退出\n");printf("%s","请输入选择:");scanf("%c",&ch);ch=toupper(ch);}while(ch!='S'&&ch!='E');switch(ch){case'S':seekkeyroot(); break; case'E':return 1; }}}。

关键路径AOE网及其如何求关键路径步骤一、关键路径（一）AOE网在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)AOE⽹具有以下两个性质：①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

另外，有些活动是可以并行进行的在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

（二）关键路径从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，⽽把关键路径上的活动称为关键活动完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延迟。

活动ai的时间余量d(i)=l(i)-e(i)，表⽰在不增加完成整个工程所需总时间的情况下，活动ai 可以拖延的时间若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动ai是关键活动由关键活动组成的路径就是关键路径（三）求关键路径的步骤（四）求所有事件的最早发生时间1.求所有事件的最早发生时间ve()（五）求所有事件的最迟发生时间1.求所有事件的最迟发生时间vl()1.求所有活动的最早发生时间e()1.求所有活动的最迟发生时间l()（八）求所有活动的时间余量（九）关键活动、关键路径的特性若关键活动耗时增加，则整个工程的工期将增长缩短关键活动的时间，可以缩短整个工程的工期当缩短到一定程度时，关键活动可能会变成非关键活动可能有多条关键路径，只提高⼀条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

关键路径的计算从源点到汇点路径长度最长的路径为该project的关键路径，即关键路径可以保证全部路径的活动都可以完毕。

ok，再次进⼊我们的作业题：例如以下图所看到的的AOE⽹（弧上权值代表活动的持续天数）1）完毕此project最少所须要多少天？2）哪些是关键活动，在图中表⽰出关键路径我们先计算最早发⽣时间ve和最迟发⽣时间vl：12345678910Ve05612151616192123Vl09612152116192123⾸先呢，编号1和编号10分别为该project的源点和汇点，我们规定最早发⽣时间ve（源点）=0，最迟发⽣时间vl（汇点）=ve（汇点）。

那么这两个量该怎样计算呢，看图：对于事件i来说，ve(i) = Max{ve(m) + dut(<m, i>)}，vl(i) = Min{vl(j) – dut(<i, j>)}；当中ve(m)代表i前⼀个事件的最早发⽣时间，dut(<m, i>)表⽰从m到i的持续时间，⼤家能够把它看成⼀个递归算法，⼀直调⽤ve()，直到ve(源点)为⽌，然后取其最⼤值，由于它要保证全部路径上的活动都能完毕；⽽最迟发⽣时间和前者⼀样，⼀直递归调⽤vl()，直到vl(汇点)为⽌，然后取其最⼩值就可以。

回到原题中对⽐例图能够⾮常快地得到表格所看到的内容。

我们再来看两个概念：e(i)和l(i)，前者为活动ai 的最早可能開始时间，后者为活动ai的最迟同意開始时间。

差别于前边的ve和vl，e和l为标识的是某活动的时间，⽽前者是某事件的时间。

假如从事件m到事件i的活动为af，则有e(f)=ve(m), l(f)=vl(i)–dut(<m,i>) ，即活动af的最早可能開始时间为其弧尾事件最早可能发⽣时间；最迟同意開始时间为其弧尾事件最迟发⽣时间与两个事件的持续时间之差。

是不是感觉有点别扭，但仅仅要理解了这⼏个关键词也就⾮常easy看懂了。

关键路径算法相关概念： （1）AOE (Activity On Edges)⽹络如果在⽆有向环的带权有向图中⽤有向边表⽰⼀个⼯程中的各项活动(Activity)，⽤边上的权值表⽰活动的持续时间(Duration)，⽤顶点表⽰事件(Event)，则这样的有向图叫做⽤边表⽰活动的⽹络，简称AOE (Activity On Edges)⽹络。

AOE ⽹是⼀个带权的有向⽆环图。

AOE⽹络在某些⼯程估算⽅⾯⾮常有⽤。

例如，可以使⼈们了解： a、完成整个⼯程⾄少需要多少时间(假设⽹络中没有环)? b、为缩短完成⼯程所需的时间, 应当加快哪些活动? （2）关键路径(Critical Path) 在AOE⽹络中, 有些活动顺序进⾏，有些活动并⾏进⾏。

从源点到各个顶点，以⾄从源点到汇点的有向路径可能不⽌⼀条。

这些路径的长度也可能不同。

完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个⼯程才算完成。

因此，完成整个⼯程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。

这条路径长度最长的路径就叫做关键路径(Critical Path)。

（3）由于实际⼯程只有⼀个开始点和⼀个结束点，因此AOE⽹存在唯⼀的⼊度为0的开始点（⼜称源点）和唯⼀的出度为0的结束点（⼜称汇点）参数定义： （1）事件的最早发⽣时间 etv（earliest time of vertex）：即顶点V k的最早发⽣时间。

（2）事件的最晚发⽣时间 ltv（latest time of vertex）：即顶点V k的最晚发⽣时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此事件将会延误整个⼯期。

（3）活动的最早开⼯时间 ete（earliest time of edge）：即弧ak的最早发⽣时间。

（4）活动的最晚开⼯时间 lte（latest time of edge）：即弧ak的最晚发⽣时间，也就是不推迟⼯期的最晚开⼯时间。