48蛤蟆的数据结构笔记之四十八的有向无环图的应用关键路径

48.蛤蟆的数据结构笔记之四十八的有向无环图的应用关键路径本篇名言：“富贵不淫贫贱乐,男儿到此是豪雄。--程颢”这次来看下有向无环图的另一个应用关键路径。1.关键路径与AOV-网相对应的是AOE-网(ActivityOnEdge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。如下图1关键路径法(CriticalPathMethod,CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。关键路径法是现代项目管理中最重要的一种分析工具。根据绘制方法的不同，关键路径法可以分为两种，即箭线图（ADM）和前导图（PDM）。箭线图（ADM）法又称为双代号网络图法，它是以横线表示活动而以带编号的节点连接活动，活动间可以有一种逻辑关系，结束-开始型逻辑关系。2.关键路径的若干基本概念下面的阐述中，设AOE网的起点为v0终点为vn.1．关键路径AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（CriticalPath），记为cp(i,j)。特别地，始点0到终点n的关键路径cp(0,n)是整个AOE的关键路径。显然，关键路径决定着AOE网的工期，关键路径的长度就是AOE网代表的工程所需的最小工期。2．事件最早/晚发生时间事件vi的最早发生时间ve(i)定义为：从始点到vi的最长（加权）路径长度，即cp(0,i)事件vi的最晚发生时间vl(i)定义为：在不拖延整个工期的条件下，vi的可能的最晚发生时间。即vl(i)=ve(n)-cp(i,n)3．活动最早/晚开始时间活动ak=vi,vj的最早开始时间e(k)：等于事件vi的最早发生时间，即e(k)=ve(i)=cp(0,i)活动ak=vi,vj的最晚开始时间l(k)定义为：在不拖延整个工期的条件下，该活动的允许的最迟开始时间，即l(k)=vl(j)–len(i,j)这里，vl(j)是事件j的允许的最晚发生时间，len(i,j)是ak的权。活动ak的最大可利用时间：定义为l(k)-e(k)4．关键活动若活动ak的最大可利用时间等于0（即(l(k)=e(k)），则称ak为关键活动，否则为非关键活动。显然，关键活动的延期，会使整个工程延期。但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。关键路径的概念，也可以用这里的关键活动定义，即有下面的：(一)基本算法关键路径算法是一种典型的动态规划法，这点在学了后面的算法设计方法后就会看到。下面就来介绍该算法。设图G=(V,E)是个AOE网，结点编号为1,2,...,n，其中结点1与n分别为始点和终点，ak=i,j∈E是G的一个活动。根据前面给出的定义，可推出活动的最早及最晚发生时间的计算方法：e(k)=ve(i)l(k)=ve(j)-len(i,j)结点的最早发生时间的计算，需按拓扑次序递推：ve(1)=0ve(j)=MAX{ve(i)+len(i,j)}对所有i,j∈E的i结点的最晚发生时间的计算，需按逆拓扑次序递推：vl(n)=ve(n)vl(i)=MIN{vl(j)-len(i,j)}对所有i,j∈E的j关于ve与vl的求法，可参阅图21-5。这种计算方法，依赖于拓扑排序，即计算ve(j)前，应已求得j的各前趋结点的ve值，而计算vl(i)前，应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边i,j（即入度减1）的同时，执行if(ve[i]+len(i,j))ve[j])ve[j]=ve[i]+len(i,j)实际上，该操作对i的每个后继j分别进行一次。因此对程序作少量扩充即可求得ve。vl的值可按类似的方法在逆拓扑排序过程（即直接按与拓扑序列相反的次序输出结点的过程）中求得，但一般不必专门这样进行。事实上，通过逆方向使用拓扑序列即可递推出各vl的值，假定拓扑序列是topoSeq，则vl的值的求法为（结点编号为1~n）。求图21-6的AOE网的所有事件的最早发生时间ee()；所有事件的最迟发生时间le()；每项活动ai的最早开始时间e()和最迟开始时间l()，完成此工程最少需要多少天？那些是关键活动，是否存在某项活动，当其提高速度后能使整个工程缩短工期?存储结构及算法设计1、在结点的定义中增加ee和le字段用于记录个事件的最早开始时间和最迟开始时间，同时得到关键路径和最小工期2、邻接矩阵中使用边权代替原来连接标志13、进行拓扑排序，形成拓扑序列1234567894、按拓扑序列顺序，从前向后搜索寻找个活动（即边），若存在该活动，则计算相应事件的最早开始时间。5、按拓扑序列顺序，从后向前搜索寻找个活动（即边），若存在该活动，则计算相应事件的最迟开始时间。6、计算各活动的最早开始时间和最迟开始时间3.代码实现3.1定义结构体typedefstructArcNode{intadjvex;//该弧指向的顶点位置structArcNode*nextarc;//指向下一个表结点intinfo;//权值信息}ArcNode;//边结点类型typedefstructVNode{VertexTypedata;intindegree;ArcNode*firstarc;}VNode,Adjlist[MaxVerNum];typedefstruct{Adjlistvertices;//邻接表intvernum,arcnum;//顶点数和弧数}ALGraph;定义结构体，同47篇笔记大同小异。3.2Main输入节点个数，输入边的个数。调用creategraph函数来创建图，调用searchmappath函数来实现关键路径。如下图2所示3.3CreateGraph根据点数，设置每个点的值。输入所有有向边的起点，终点和权值。根据邻接表的方式创建整个图。3.4SearchMapPath定义数组Ve表示最早发生时间，数组V1表示最晚发生时间。先设置每个点的最早发生时间都为0。然后循环从第一个点开始，获取该点的第一个链接的边。如果链接的边不为NULL，则获取边另外一段的点。判断Ve[i]+p-infoVe[k](判断该边最早发生的值加上到下一边的权值是不是大于下一边本省的最早发生值)，如果大于说明下一边的最早发生值要发生变化。接着基础处理和点i链接的其他点，以此循环。直到没有点和点i相连。然后处理i+1个点开始。结束后得到每个点的关键路径值，即Ve数组。然后是求最迟发生的时间：将数组V1都赋值为Ve[]数组的最后一个值，也即整个项目的最短周期。然后倒推，获取倒数第二个点i，得到i点的第一条边，如果边存在，则判断V1[k]-p-infoV1[i](判断边另一端的最晚周期减去边的权值是否小于i点的最小权值)，如果小于，说明i点的最晚周期需要缩小，不然到i点在执行的权值就会超过项目最晚周期。接着处理i点相连的其他点（是从i点出发的链接的点）。如果i点处理完，就处i-1的点。最后输出，从第一个点i开始，得到和第一个点相连的点k。然后判断Ve[i]和V1[k]-p-info如果相同则表示i点开始到k点的路径是关键路径。因为Ve[i]本身是关键路径，而V1[k]是K的最晚发生时间，p-info是i到k的权值，V1[k]-p-info=Ve[i],表示K点最晚发生的时间点减去与i点相连边的权值与Ve[i]（关键路径）相等。说明i到k点中间没有油水可以挤出来了。以此循环。最后删除数组Ve,V1.4.源码#includestdio.h#includestdlib.h#defineMaxVerNum20intvisited[MaxVerNum];typedefcharVertexType;typedefstructArcNode{intadjvex;//该弧指向的顶点位置structArcNode*nextarc;//指向下一个表结点intinfo;//权值信息}ArcNode;//边结点类型typedefstructVNode{VertexTypedata;intindegree;ArcNode*firstarc;}VNode,Adjlist[MaxVerNum];typedefstruct{Adjlistvertices;//邻接表intvernum,arcnum;//顶点数和弧数}ALGraph;//查找符合的数据在数组中的下标intLocateVer(ALGraphG,charu){inti;for(i=0;iG.vernum;i++){if(u==G.vertices[i].data)returni;}if(i==G.vernum){printf(Erroru!\n);exit(1);}return0;}//常见图的邻接矩阵voidCreateALGraph(ALGraph&G){inti,j,k,w;charv1,v2;ArcNode*p;printf(输入顶点数和弧数:);scanf(%d%d,&G.vernum,&G.arcnum);printf(请输入顶点!\n);for(i=0;iG.vernum;i++){printf(请输入第%d个顶点:\n,i);fflush(stdin);scanf(%c,&G.vertices[i].data);G.vertices[i].firstarc=NULL;G.vertices[i].indegree=0;}for(k=0;kG.arcnum;k++){printf(请输入弧的顶点和相应权值(v1,v2,w):\n);//清空输入缓冲区fflush(stdin);scanf(%c%c%d,&v1,&v2,&w);i=LocateVer(G,v1);j=LocateVer(G,v2);p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=w;p-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;G.vertices[j].indegree++;//vi-vj,vj入度加1}return;}//求图的关键路径函数voidCriticalPath(ALGraphG){inti,k,e,l;int*Ve,*Vl;ArcNode*p;//*****************************************//以下是求时间最早发生时间//*****************************************Ve=newint[G.vernum];Vl=newint[G.vernum];for(i=0;iG.vernum;i++)//前推Ve[i]=0;for(i=0;iG.vernum;i++){ArcNode*p=G.vertices[i].firstarc;while(p!=NULL){k=p-adjvex;if(Ve[i]+p-infoVe[k])Ve[k]=Ve[i]+p-info;p=p-nextarc;}}//*****************************************//以下是求最迟发生时间//*****************************************for(i=0;iG.vernum;i++)Vl[i]=Ve[G.vernum-1];for(i=G.vernum-2;i=0;i--)//后推{p=G.vertices[i].firstarc;while(p