《关键路径算法》PPT课件.ppt
关键路径,与AOV-网相对应的是AOE-网(Activity On Edge)即边表示活动的网。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-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。假设开始点是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由弧表示，其持续时间记为dut(),则有如下关系：e(i)=ve(j)(7-1)l(i)=vl(k)-dut()求ve(j)和vl(j)需分两步进行：（1）从ve(0)开始向前递推 ve(j)=Maxve(i)+dut()i T,j=1,2,3,n-1（7-2）其中，T是所有以第j个顶点为尾的弧的结合。（2）从vl(n-1)=ve(n-1)起向后递推 vl(i)=Min vl(j)dut()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条弧，建立AOE-网的存储结构；(2)从源点v0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei(1in-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。(3)从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli(n2i2)；(4)根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间 l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。先将拓扑排序算法7.12改写成算法7.13，则算法7.14便为求关键路径的算法。,/*图的关键路径问题的算法AOE.C*/#include#include#define MAXVEX 100#define TRUE 1#define FALSE 0typedef char VertexTypeMAXVEX;/*存放顶点信息的字符串*/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,arcnum;/*图的顶点个数*/ALGraph;,/*求出图中所有顶点的入度，方法是搜索整个邻接表*/void FindInDegree(ALGraph G,int inDegree)int i;ArcNode*p;for(i=0;iadjvex+;p=p-nextarc;,void makeNewAOV(ArcNode*p,int*indegree,int,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;,while(top!=-1)/*栈不为空*/j=top;top=indegreetop;/*取出当前栈顶元素*/topocount+=j;/*ptopo数组存放拓扑序列*/p=G.verticesj.firstarc;/取该元素边表中的第一个边结点，删除该结点,构造新的AOV网 makeNewAOV(p,indegree,top);/对indegree数组进行修改 if(countG.vexnum)/*AOV网中存在回路*/printf(The aov network has a cyclen);return FALSE;printf(拓扑序列为：);/输出拓扑序列 for(i=0;iG.vexnum;i+)printf(V%1d,topoi+1);printf(n);return TRUE;,void insert(ALGraph,void makeList(ALGraph,#define MAXEDGE 100/*MAXEDEG为边的最大数目*/void countve(ALGraph G,int*topo,AdjType*ve)/*计算各事件的最早发生时间*/int i,j,k;ArcNode*p;for(i=0;iadjvex;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;i=0;k-)/*下标从0开始，最后一个顶点无后继，所以减2*/i=topok;p=G.verticesi.firstarc;while(p!=NULL)j=p-adjvex;if(vlj-p-weightweight;p=p-nextarc;,void counte_l(ALGraph G,AdjType*ve,AdjType*vl,AdjType*ee,AdjType*el)/*计算各活动的最早发生时间和最迟发生时间，并输出关键路径*/int i=0,j,k;ArcNode*p;printf(关键路径是：);for(j=0;jadjvex;eei=vej;eli=vlk-p-weight;if(eei=eli)printf(,j+1,k+1);i+;/i表示弧的序号。弧的序号自第一个顶点开始到最后一个顶点止顺序编号。p=p-nextarc;,int CriticalPath(ALGraph G)/*关键路径算法*/AdjType veMAXVEX,vlMAXVEX,eeMAXEDGE,elMAXEDGE;int topoMAXVEX;if(topoSort(G,topo)=FALSE)/*求AOE网的一个拓扑序列*/return FALSE;/*若有环则返回FALSE*/countve(G,topo,ve);/*计算数组ve，ve存放事件可能的最早发生时间*/countvl(G,topo,ve,vl);/*计算数组vl，vl存放事件可能的最迟发生时间*/counte_l(G,ve,vl,ee,el);/*计算数组ee,el并输出结果*/printf(n);/*数组ee存放活动的最早开始时间,数组el存放活动的最晚开始时间*/return TRUE;,void main()/*主程序*/ALGraph G;makeList(G);if(CriticalPath(G)=FALSE)printf(There is no critical path!n);,各事件的最早发生时间数组ve变化情况,各事件的最迟发生时间数组vl变化情况,各事件和各活动的最早与最迟开始时间,输出：拓扑序列为：v1 v3 v4 v6 v2 v5 v8 v7 v9关键路径是：，即有两条关键路径：（v1，v2，v5，v7，v9）和（v1，v2，v5，v8，v9）,实践已经证明：用AOE-网来估算某些工程完成的时间是非常有用的。实际上，求关键路径的方法本身最初就是与维修和建造工程一起发展的。但是，由于网中各项活动是互相牵涉的，因此，影响关键活动的因素亦是多方面的，任何一项活动持续时间的改变都会影响关键路径的改变。由此可见，关键活动的速度提高是有限度的。只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。另一方面，若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。,
