最新AOE关键路径汇总.docx

1、最新AOE关键路径汇总AOE关键路径6.4.4 关键路径一、AOE网与AOV-网相对应的是AOE-网(Activity On Edge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。例如，图6.22是一个假想的有11项活动的AOE-网。其中有9个事件v0，v1，v2，v8，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v0表示整个工程开始，v8表示整个工程结束，v4表示a4和a5已经完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a

2、1需要6天，a2需要4天等。图6.22 一个AOE网和AOV-网不同，对AOE-网有待研究的问题是： (1)完成整项工程至少需要多少时间? (2)哪些活动是影响工程进度的关键? 由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。假设开始点是v0，从v0到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活

3、动的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。例如在图6.22中，v0是源点，v8是汇点，关键路径有两条：(v0，v1，v4，v6，v8)或(v0，v1，v4，v7，v8)，长序均为18。关键活动为(a1，a4，a7，a10)或(a1，a4，a8，a11)。比如，关键活动a1需要6

4、天完成，如果a1提前1天，整个工程也可提前1天完成。所以不论是估算工期，还是研究如何加快工程进度，主要问题就在于找到AOE-网的关键路径。如何确定关键路径，首先定义4个描述量。(1)事件vi的最早发生时间ve(i)进入事件vi的每一活动都结束，vi才可发生，所以ve(i)是从源点到vi的最长路径长度。求ve(i)的值，可根据拓扑顺序从源点开始到汇点递推，通常将工程开始顶点事件v0的最早发生时间定义为0，即： ve(0)=0 ve(i)=Maxve(k) + wk,i T，1in-1其中，T是所有以vi为头的弧的集合，wk,i是弧的权值，即对应活动的持续时间。(2)事件vi的最迟发生时间vl(i

5、)事件vi的发生不得延误vi的每一后继事件的最迟发生时间。为了不拖延工期，vi的最迟发生时间不得迟于其后继事件vk的最迟发生时间减去活动的持续时间。求出ve(i)后可根据逆拓扑顺序从汇点开始向源点递推，求出vl(i)。vl(n-1)=ve(n-1)vl(i)=Minvl(k)wi,k S，0in-2其中，S是所有以vi为尾的弧的集合，wi,k是弧的权值。(3)活动ai=的最早开始时间e(i)只有事件vj发生了，活动ai才能开始。所以，活动ai的最早开始时间等于事件vj的最早发生时间ve(j)，即： e(i)=ve(j)(4)活动ai=的最晚开始时间l(i)活动ai的开始时间需保证不延误事件vk

6、的最迟发生时间。所以活动ai的最迟开始时间l(i)等于事件vk的最迟发生时间vl(k)减去活动ai的持续时间wj,k，即： l(i)=vl(k)wj,k显然，对于关键活动而言，e(i)= l(i)。对于非关键活动，l(i)e(i)的值是该工程的期限余量，在此范围内的适度延误不会影响整个工程的工期。一个活动ai的最晚开始时间l(i)和最早开始时间e(i)的差值l(i)e(i)是该活动完成的时间余量。它是在不增加完成整个工程所需的总时间的情况下，活动ai可以拖延的时间。当一活动的时间余量为零时，说明该活动必须如期完成，否则就会拖延整个工程的进度。所以称l(i)e(i)=0，即l(i)=e(i)时的

7、ai是关键活动。二、关键路径求解的过程(1)输入e条弧，建立AOE-网的存储结构。 (2)从源点v0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei (1in-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。 (3)从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli(n2i2)；(4)根据各顶点的ve和vl值，求每条弧（活动）ai的最早开始时间e(i)和最迟开始时间l(i)。(5)找出e(i)=l(i)的活动，则为关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路

8、径，关键路径有可能不止一条。三、关键路径算法的实现由于每个事件的最早发生时间ve(i)和vl(i)要在拓扑序列的基础上进行计算，所以关键路径算法的实现要基于拓扑排序算法，我们仍采用邻接表做有向图的存储结构。算法的实现要引入以下辅助的数据结构：(1)一维数组ve(i)：事件vi的最早发生时间。(2)一维数组vl(i)：事件vi的最迟发生时间。(3)一维数组topo(i)：记录拓扑序列的顶点序号。【算法思想】(1)调用拓扑排序算法，使拓扑序列保存在topo中。(2)将每个事件的最早发生时间ve(i)初始化为0，vei=0。(3)根据topo中的值，按从前向后的拓扑次序依次求每个事件的最早发生时间。

9、取得拓扑序列中的顶点k，k=topoi；用指针p依次指向k的每个邻接顶点，取得每个邻接顶点的序号j=p-adjvex，依次更新顶点j的最早发生时间vej：if(vejweight) vej= vek+p-weight;(4)将每个事件的最迟发生时间vl(i)初始化为汇点的最早发生时间，vli=ve(n-1)。(5)根据topo中的值，按从后向前的逆拓扑次序依次求每个事件的最迟发生时间vli。取得拓扑序列中的顶点k，k=topoi；用指针p依次指向k的每个邻接顶点，取得每个邻接顶点的序号j=p-adjvex，依次更新顶点k的最迟发生时间：if(vlkweight) vlk= vljp-weigh

10、t;(6)从源点开始，对于每个顶点i，用指针p依次指向i的每个邻接顶点，取得每个顶点的序号j=p-adjvex，分别计算活动的最早发生时间和最迟发生时间e和l。 e=vei； l=vljp-weight;如果e和l相等，则活动为关键活动，输出弧。【算法6.13】图的关键路径问题的算法之一AOE.CPP/*2013年5月14日修改*图的关键路径问题的算法之一AOE.CPP*/#include #define MAXVEX 100#define TRUE 1#define FALSE 0typedef char VertexTypeMAXVEX; /存放顶点信息的字符串typedef struct

11、 ArcNode int adjvex; /相邻顶点字段 float weight; struct ArcNode *nextarc; / 链字段ArcNode; / 边表中的结点typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 边表头指针VNode,AdjListMAXVEX; / 顶点表中的结点typedef struct AdjList vertices; int vexnum,arcnum; /图的顶点个数和弧的条数ALGraph;/* 求出图中所有顶点的入度，方法是搜索整个邻接表 */void Find

12、InDegree(ALGraph G,int inDegree) int i; ArcNode *p; for(i=0;iG.vexnum;i+) inDegreei=0; /顶点入度数组赋初值 for(i=0;iadjvex+; p=p-nextarc; int TopologicalSort(ALGraph G,int *topo) /拓扑排序算法 ArcNode *p; int i,j,k,count=0,top=-1; int indegreeMAXVEX; FindInDegree(G,indegree); / 求出图中所有顶点的入度 for(i=0;iadjvex; indegre

13、ek-; if(indegreek=0) /将新的入度为零的边入栈 indegreek=top; top=k; p=p-nextarc; if(countG.vexnum) /AOV网中存在回路 coutThe aov network has a cyclen; return FALSE; cout拓扑序列为： ; for(i=0;iG.vexnum;i+) coutVtopoi ; coutadjvex=b; temp-nextarc=NULL; temp-weight=weight; p=G.verticesa.firstarc; if(p=NULL) G.verticesa.firsta

14、rc=temp; else while(p-nextarc!=NULL) p=p-nextarc; /找表尾 p-nextarc=temp; int CriticalPath(ALGraph G)/G为有向网，输出G的各项关键活动。 int i,k,j,n,topoMAXVEX; ArcNode *p; float veMAXVEX,vlMAXVEX,e,l; if(!TopologicalSort(G,topo) return FALSE; /调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回FALSE n=G.vexnum; /n为顶点个数 for(i=0;in;

15、i+) vei=0; /初始化顶点事件的最早发生时间/*-按拓扑次序求每个事件的最早发生时间- */ for(i=0;iadjvex; /j为邻接顶点的序号 if(vejweight) /更新顶点j的最早发生时间vejvej=vek+p-weight; p=p-nextarc; /p指向k的下一个邻接顶点 /while /for for(i=0;i=0;i-) k=topoi; /取得拓扑序列中的顶点序号k p=G.verticesk.firstarc; /p指向k的第一个邻接顶点 while(p!=NULL) /依次更新k的所有邻接点的最迟发生时间 j=p-adjvex; /j为邻接顶点的序

16、号 if(vlkvlj-p-weight) /更新顶点k的最迟发生时间vlk vlk=vlj-p-weight; p=p-nextarc; /p指向k的下一个邻接顶点 /while /for/*-判断每一活动是否为关键活动- */ for(i=0;iadjvex; /j为i的邻接顶点的序号 e=vei; /计算活动的最早开始时间 l=vlj-p-weight; /计算活动的最迟开始时间 if(e=l) coutG.verticesi.data，G.verticesj.data,; p=p-nextarc; /p指向i的下一个邻接顶点 /while /for return TRUE;/Criti

17、calPathvoid main() /主函数 ALGraph G=V0,NULL,V1,NULL,V2,NULL,V3,NULL,V4,NULL, V5,NULL,V6,NULL,V7,NULL,V8,NULL; /顶点初始化 G.vexnum=9; insert(G,0,1,6); insert(G,0,3,5); insert(G,0,2,4); insert(G,1,4,1); insert(G,2,4,1); insert(G,3,5,2); insert(G,4,6,9); insert(G,4,7,7); insert(G,5,7,4); insert(G,6,8,2); ins

18、ert(G,7,8,4); if(CriticalPath(G)=FALSE) coutThere is no critical path!n;拓扑序列为：v0 v2 v3 v5 v1 v4 v7 v6 v8，有两条关键路径：(v0，v1，v4，v6，v8)和(v0，v1，v4，v7，v8)图的关键路径问题的算法之二AOE.CPP/*2013年4月29日修改*图的关键路径问题的算法AOE.CPP*/#include #define MAXVEX 100#define TRUE 1#define FALSE 0typedef char VertexTypeMAXVEX; /*存放顶点信息的字符串

19、*/typedef float AdjType;typedef struct ArcNode int adjvex; /* 相邻顶点字段 */ AdjType weight; struct ArcNode *nextarc; /* 链字段 */ArcNode; /* 边表中的结点 */typedef struct VNode VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 边表头指针 */VNode,AdjListMAXVEX; /* 顶点表中的结点 */typedef struct AdjList vertices; int vexnum,

20、arcnum; /* 图的顶点个数 */ALGraph;/* 求出图中所有顶点的入度，方法是搜索整个邻接表 */void FindInDegree(ALGraph G,int inDegree) int i; ArcNode *p; for(i=0;iG.vexnum;i+) inDegreei=0; /*顶点入度数组赋初值*/ for(i=0;iadjvex+; p=p-nextarc; void makeNewAOV(ArcNode *p,int *indegree, int &top) int k; while(p) /* 删除以该顶点为起点的边 */ k=p-adjvex; indeg

21、reek-; if(indegreek=0) /* 将新的入度为零的边入栈 */ indegreek=top; top=k; p=p-nextarc; int topoSort(ALGraph G,int *topo) /*拓扑排序算法*/ ArcNode *p; int i,j,count=0,top=-1; int indegreeMAXVEX; FindInDegree(G,indegree); /* 求出图中所有顶点的入度 */ for(i=0;iG.vexnum;i+) if(indegreei=0) /* 将入度为零的顶点入栈 */ indegreei=top; top=i; wh

22、ile(top!=-1) /* 栈不为空 */ j=top; top=indegreetop; /* 取出当前栈顶元素 */ topocount+=j; /*ptopo数组存放拓扑序列*/ p=G.verticesj.firstarc; /* 取该元素边表中的第一个边结点，删除该结点,构造新的AOV网*/ makeNewAOV(p,indegree,top); /*对indegree数组进行修改*/ if(countG.vexnum) /* AOV网中存在回路 */ coutThe aov network has a cyclen; return FALSE; cout拓扑序列为： ; for

23、(i=0;iG.vexnum;i+) coutVtopoi+1 ; coutadjvex=b; temp-nextarc=NULL; temp-weight=weight; p=G.verticesa.firstarc; if(p=NULL) G.verticesa.firstarc=temp; else while(p-nextarc!=NULL) p=p-nextarc; /*找表尾*/ p-nextarc=temp; void makeList(ALGraph &G) /*邻接表的构造*/ int i; G.vexnum=9; for(i=0;iG.vexnum;i+) /*给顶点指针域

24、赋初值*/ G.verticesi.firstarc=NULL; insert(G,0,1,6); insert(G,0,3,5); insert(G,0,2,4); insert(G,1,4,1); insert(G,2,4,1); insert(G,3,5,2); insert(G,4,6,9); insert(G,4,7,7); insert(G,5,7,4); insert(G,6,8,2); insert(G,7,8,4);#define MAXEDGE 100 /*MAXEDEG为边的最大数目*/void countve(ALGraph G,int *topo,AdjType *v

25、e) /* 计算各事件的最早发生时间*/ int i,j,k; ArcNode *p; for(i=0;iG.vexnum;i+) vei=0; /*ee数组赋初值*/ for(k=0;kadjvex; if(vei+p-weightvej) vej=vei+p-weight; p=p-nextarc; void countvl(ALGraph G,int *topo,AdjType *ve, AdjType *vl) /*计算各事件的最迟发生时间*/ int i,j,k; ArcNode *p; for(i=0;iG.vexnum;i+) /*求事件vi允许的最迟发生时间vl(i) */ vli=veG.vexnum-1; /*每个事件的最迟发生时间赋初值为最生事件的最早发生时间