AOE关键路径

7.5.2关键路径•与AOV-网相对应的是AOE-网(ActivityOnEdge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。•例如，图7.29是一个假想的有11项活动的AOE-网。其中有9个事件v1，v2，v3，…，v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v1表示整个工程开始，v9表示整个工程结束，v5表示a4和a5已经完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天等。•和AOV-网不同，对AOE-网有待研究的问题是：•(1)完成整项工程至少需要多少时间?•(2)哪些活动是影响工程进度的关键?•由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(CriticalPath)。假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。•由上分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得AOE-网中活动的e(i)和l(i)，首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧j,k表示，其持续时间记为dut(j,k),则有如下关系：•e(i)=ve(j)(7-1)•l(i)=vl(k)-dut(j,k)•求ve(j)和vl(j)需分两步进行：•（1）从ve(0)开始向前递推•ve(j)=Max{ve(i)+dut(i,j)}•i•i,j∈T,j=1,2,3,…,n-1（7-2）•其中，T是所有以第j个顶点为尾的弧的结合。•（2）从vl(n-1)=ve(n-1)起向后递推•vl(i)=Min{vl(j)–dut(i,j)}•j•i,j∈S,i=n-2,…,0（7-3）•其中，S是所有以第i个顶点为头的弧的集合。•这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。因此，可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。•由此得到求关键路径的算法：•(1)输入e条弧j，k，建立AOE-网的存储结构；•(2)从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i](1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。•(3)从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n—2≥i≥2)；•(4)根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。•先将拓扑排序算法7.12改写成算法7.13，则算法7.14便为求关键路径的算法。•/*图的关键路径问题的算法AOE.C*/•#includestdio.h•#includestdlib.h•#defineMAXVEX100•#defineTRUE1•#defineFALSE0•typedefcharVertexType[MAXVEX];/*存放顶点信息的字符串*/•typedeffloatAdjType;•typedefstructArcNode•{intadjvex;/*相邻顶点字段*/•AdjTypeweight;•structArcNode*nextarc;/*链字段*/•}ArcNode;/*边表中的结点*/•typedefstructVNode•{VertexTypedata;/*顶点信息*/•ArcNode*firstarc;/*边表头指针*/•}VNode,AdjList[MAXVEX];/*顶点表中的结点*/•typedefstruct•{AdjListvertices;•intvexnum,arcnum;/*图的顶点个数*/•}ALGraph;•/*求出图中所有顶点的入度，方法是搜索整个邻接表*/•voidFindInDegree(ALGraphG,intinDegree[])•{inti;•ArcNode*p;•for(i=0;iG.vexnum;i++)inDegree[i]=0;/*顶点入度数组赋初值*/•for(i=0;iG.vexnum;i++)•{p=G.vertices[i].firstarc;•while(p)•{inDegree[p-adjvex]++;•p=p-nextarc;•}•}•}•voidmakeNewAOV(ArcNode*p,int*indegree,int&top)•{intk;•while(p)/*删除以该顶点为起点的边*/•{k=p-adjvex;•indegree[k]--;•if(indegree[k]==0)/*将新的入度为零的边入栈*/•{indegree[k]=top;•top=k;•}•p=p-nextarc;•}•}•inttopoSort(ALGraphG,int*topo)/*拓扑排序算法*/•{ArcNode*p;•inti,j,count=0,top=-1;•intindegree[MAXVEX];•FindInDegree(G,indegree);/*求出图中所有顶点的入度*/•for(i=0;iG.vexnum;i++)•if(indegree[i]==0)//将入度为零的顶点入栈•{indegree[i]=top;•top=i;•}•while(top!=-1)/*栈不为空*/•{j=top;•top=indegree[top];/*取出当前栈顶元素*/•topo[count++]=j;/*ptopo数组存放拓扑序列*/•p=G.vertices[j].firstarc;•//取该元素边表中的第一个边结点，删除该结点,构造新的AOV网•makeNewAOV(p,indegree,top);//对indegree数组进行修改•}•if(countG.vexnum)/*AOV网中存在回路*/•{printf(Theaovnetworkhasacycle\n);•returnFALSE;•}•printf(拓扑序列为：);//输出拓扑序列•for(i=0;iG.vexnum;i++)printf(V%1d,topo[i]+1);printf(\n);•returnTRUE;•}•voidinsert(ALGraph&G,inta,intb,floatweight)•/*在表尾插入表结点*/•{ArcNode*p,*temp;•temp=(ArcNode*)malloc(sizeof(ArcNode));•temp-adjvex=b;•temp-nextarc=NULL;•temp-weight=weight;•p=G.vertices[a].firstarc;•if(p==NULL)•G.vertices[a].firstarc=temp;•else•{while(p-nextarc!=NULL)p=p-nextarc;/*找表尾*/•p-nextarc=temp;•}•}•voidmakeList(ALGraph&G)/*邻接表的构造*/•{inti;•G.vexnum=9;•for(i=0;iG.vexnum;i++)//给顶点指针域赋初值•G.vertices[i].firstarc=NULL;•insert(G,0,1,6);insert(G,0,2,4);insert(G,0,3,5);•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);•}•#defineMAXEDGE100/*MAXEDEG为边的最大数目*/•voidcountve(ALGraphG,int*topo,AdjType*ve)/*计算各事件的最早发生时间*/•{inti,j,k;•ArcNode*p;•for(i=0;iG.vexnum;i++)ve[i]=0;/*ee数组赋初值*/•for(k=0;kG.vexnum;k++)/*求事件vj可能的最早发生时间ee(j)*/•{i=topo[k];//k仅起控制作用•p=G.vertices[i].firstarc;•while(p!=NULL)•{j=p-adjvex;•if(ve[i]+p-weightve[j])ve[j]=ve[i]+p-weight;•p=p-nextarc;•}•}•}•voidcountvl(ALGraphG,int*topo,AdjType*ve,AdjType*vl)/*计算各事件的最迟发生时间*/•{inti,j,k;ArcNode*p;•for(i=0;iG.vexnum;i++)//求事件vi允许的最迟发生时间vl(i)•vl[i]=ve[G.vexnum-1];/*每个事件的最迟发生时间赋初值为最生事件的最早发生时间（本例均为18）*/•for(k=G.vexnum-2;k=0;k--)/*下标从0开始，最后一个顶点无后继，所以减2*/•{i=topo[k];•p=G.vertices[i].firstarc;•while(p!=NULL)•{j=p-adjvex;•if(vl[j]-p-weightvl[i])vl[i]=vl[j]-p-weight;•p=p-nextarc;•}•}•}•voidcounte_l(ALGraphG,AdjType*ve,AdjType*vl,AdjType*ee,AdjType*el)•/*计算各活动的最早发生时间和最迟发生时间，并输出关键路径*/•{inti=0,j,k;ArcNode*p;•printf(关键路径是：);•for(j=0;jG.vexnum;j++)/*求活动ai的最早开始时间ee(i)及最晚开始时间el(i)*/•{p=G.vertices[j].firstarc;•while(p!=NULL)•{k=p-adjvex;•ee[i]=ve[j];•el[i]=vl[k]-p-weight;•if(ee[i]==el[i])printf(v%1d,v%1d,,j+1,k+1);•i++;//i表示弧的序号。弧的序号自第一个顶点开始到最后一个顶点止顺序编号。•p=p-nextarc;•}}}•intCriticalPath(ALGraphG)/*关键路径算法*/•{AdjTypeve[MAXVEX],vl[MAXVEX],ee[MAXEDGE],el[MAXEDGE];•inttopo[MAXVEX];•if(topoSort(G,topo)==FALSE)/*求AOE网的一个拓扑序列*/•returnFALSE;/*若有环则返回FALSE*/•countve(G,topo,ve);/