48. 数据结构笔记之四十八的有向无环图的应用关键路径_无向无环图, 可达性分析

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

“富贵不淫贫贱乐 , 男儿到此是豪雄。-- 程颢”

来看下有向无环图的另一个应用关键路径。

1.  关键路径

与AOV-网相对应的是AOE-网(Activity On Edge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。

           如下图1

关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法，是网络图计划方法的一种，属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。关键路径法是现代项目管理中最重要的一种分析工具。

根据绘制方法的不同，关键路径法可以分为两种，即箭线图（ADM）和前导图（PDM）。

箭线图（ADM）法又称为双代号网络图法，它是以横线表示活动而以带编号的节点连接活动，活动间可以有一种逻辑关系，结束-开始型逻辑关系。

 

 

2.  关键路径的若干基本概念

下面的阐述中，设AOE网的起点为v0终点为vn.

1．关键路径

AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（Critical Path），记为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)= 0

                 ve(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、邻接矩阵中使用边权代替原来连接标志1

3、进行拓扑排序，形成拓扑序列

1 2 3 4 5 6 7 8 9

4、按拓扑序列顺序，从前向后搜索寻找个活动（即边），若存在该活动，则计算相应事件的最早开始时间。

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.2      Main

输入节点个数，输入边的个数。

调用creategraph函数来创建图，调用searchmappath函数来实现关键路径。

如下图2所示

3.3      CreateGraph

根据点数，设置每个点的值。

输入所有有向边的起点，终点和权值。

根据邻接表的方式创建整个图。

3.4      SearchMapPath

定义数组Ve表示最早发生时间，数组V1表示最晚发生时间。

先设置每个点的最早发生时间都为0。

然后循环从第一个点开始，获取该点的第一个链接的边。

如果链接的边不为NULL，则获取边另外一段的点。

判断Ve[i]+ p->info > Ve[k] (判断该边最早发生的值加上到下一边的权值是不是大于下一边本省的最早发生值 )，如果大于说明下一边的最早发生值要发生变化。

接着基础处理和点i链接的其他点，以此循环。直到没有点和点i相连。

然后处理i+1个点开始。

结束后得到每个点的关键路径值，即Ve数组。

然后是求最迟发生的时间：

将数组V1都赋值为Ve[]数组的最后一个值，也即整个项目的最短周期。

然后倒推，获取倒数第二个点i，得到i点的第一条边，如果边存在，则判断

V1[k]-p->info <V1[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.  源码

#include<stdio.h>

#include<stdlib.h>

#defineMaxVerNum20

 

int visited[MaxVerNum];

 

typedefcharVertexType;

 

typedefstructArcNode

{

           intadjvex;                                        //该弧指向的顶点位置

           structArcNode *nextarc;         //指向下一个表结点

           intinfo;                                     //权值信息

}ArcNode;                                             //边结点类型

 

typedefstructVNode

{

           VertexTypedata;

           intindegree;

           ArcNode *firstarc;

}VNode,Adjlist[MaxVerNum];

 

typedefstruct

{

           Adjlistvertices;           //邻接表

           intvernum, arcnum;            //顶点数和弧数

}ALGraph;

 

//查找符合的数据在数组中的下标

int LocateVer(ALGraphG,charu)

{

           inti;

           for(i= 0; i <G.vernum; i++)

           {

                     if(u==G.vertices[i].data)

                                returni;

           }

           if(i==G.vernum)

           {

                     printf("Erroru!\n");

                     exit(1);

           }

           return0;

}

 

//常见图的邻接矩阵

void CreateALGraph(ALGraph&G)

{

           inti, j, k, w;

           charv1, v2;

           ArcNode *p;

           printf("输入顶点数和弧数: ");

           scanf("%d%d", &G.vernum,&G.arcnum);

           printf("请输入顶点!\n");

           for(i= 0; i <G.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; k <G.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;

}

 

//求图的关键路径函数

void CriticalPath(ALGraphG)

{

           inti, k, e, l;

           int *Ve, * Vl;

           ArcNode *p;

 

           //*****************************************

           //以下是求时间最早发生时间

           //*****************************************

 

           Ve =newint [G.vernum];

           Vl =newint [G.vernum];

 

           for(i= 0; i <G.vernum; i++)             //前推

                     Ve[i]= 0;

 

           for(i= 0; i <G.vernum; i++)

           {

                     ArcNode *p =G.vertices[i].firstarc;

                     while(p!=NULL)

                     {

                                k= p->adjvex;

                                if(Ve[i]+ p->info > Ve[k])

                                          Ve[k]= Ve[i]+p->info;

                                p= p->nextarc;

                     }

           }

           //*****************************************

           //以下是求最迟发生时间

           //*****************************************

           for(i= 0; i <G.vernum; i++)

                     Vl[i]= Ve[G.vernum-1];

           for(i=G.vernum-2; i >= 0; i--)                //后推

           {

                     p= G.vertices[i].firstarc;

                     while(p!=NULL)

                     {

                                k= p->adjvex;

                                if(Vl[k]- p->info < Vl[i])

                                          Vl[i]= Vl[k] - p->info;

                                p= p->nextarc;

                     }

           }

           //******************************************

           for(i= 0; i <G.vernum; i++)

           {

                     p= G.vertices[i].firstarc;

                     while(p!=NULL)

                     {

                                k= p->adjvex;

                                e= Ve[i];             //最早开始时间为时间vi的最早发生时间

                                l= Vl[k] - p->info;            //最迟开始时间

                                chartag = (e == l) ?'*' :' ';//关键活动

                                printf("(%c,%c), e = %2d, l = %2d, %c\n",G.vertices[i].data,G.vertices[k].data,e, l, tag);

                                p= p->nextarc;

                     }

           }

           delete[] Ve;

           delete[] Vl;

}

 

void main()

{

           ALGraphG;

           printf("图的关键路径\n");

           CreateALGraph(G);

           CriticalPath(G);

}

 

 

5.  关键路径历史

关键路径法（CPM）最早出现于1956年，当时杜邦当时美国杜邦（Du Pont）公司拥有一台UNIVAC 1 计算机，他们使用这台计算机进行他们公司几乎所有的数据处理工作，但是仍然还有大量的剩余时间，杜邦（Du Pont）公司的管理层开始研究计算机在其它方面使用的可能性，因为当时电脑的费用是非常高昂的，他们考虑工程计划可能是应用电脑的一个方向。

他们联系了雷明顿兰德（Remington Rand）公司的Macuchy 博士，帮他们解决计算机使用的问题，后者派出了年轻的数学家James E. Kelly去协助杜邦（Du Pont）公司解决问题，杜邦公司方面的负责人是Morgan Walker。

他们要解决的问题是在工程项目中工期和费用之间的关系，他们研究的是如何能够采取正确的措施，在减少工期的情况下能尽可能少的增加费用。1957年5月7日，在特拉华州内瓦克召开的一个会议正式确定开始新计划技术的开发。Kelly借用了线性规划的概念来解决项目计划自动计算的问题，简单的说就是确定了每个活动的工期和活动间的逻辑关系，输入电脑后就能自动计算项目的工期，为了电脑的计算，Kelly在活动间使用了i，j这样的节点来表示活动间的前后逻辑关系。

当时遇到的一个问题是，杜邦公司的管理层并不理解Kelly所使用的方法，为了让其他人能够理解所使用方法的原理，Kelly就绘制了图形来解释电脑所作的工作，图形以箭线表示活动，以节点表示活动间的逻辑关系，这就是最早的箭线图（ADM）。

前面提到过，Kelly和Walker最初研究的目的是为了解决项目中工期和费用之间关系的问题，所以在Kelly和Walker最初提出的方法中，也包括费用的计划方法，其做法是，在每个活动上加载其相应的费用，从而得到整个项目的费用，就能分析与进度相关的费用问题，这种做法与现在所用的方法没有太大差别。不过，在当时的情况下，项目收集费用并分解到各个活动上存在较大困难。所以，在之后的很长时期内，关键路径法主要还是用于进度的计划和控制方面。Kelly和Walker还提出了资源加载和分配的方法，当然也存在和费用分析一样的问题。

尽管存在这些问题，在1957年7月24日，他们已经做了一个简化的例子，称为”George Fischer Works”，这个计划包括了61条活动，其中有8个时间限制和16条虚工作。在刚开发出这种方法时，他们将这种方法称为Kelly-Walker法，而计划中的关键线路，他们称之为主链路（Main chain）。

根据Kelly和Walker的论文和其它相关书籍的记载，当时他们一共进行了三个试验对Kelly-Walker法进行检验。第一个试验是在1957年12月份，杜邦公司成立了一个测试小组对这种新的计划方法测试，有一个传统的计划组与他们同时独立对一个价值1000万美元的化学设备项目进行计划。这个测试小组的成员没有参与Kelly-Walker法的开发，但是在开始测试之前，他们接受40个小时的培训。此项目的计划从初步设计的完成开始，在编制计划时，他们首先将整个项目分解成一些较小的工作包，然后再将这些工作包最终分解成为活动，项目共有800条活动，其中包括400条施工活动，150条采购和设计活动。根据记载，在此项目中显示出的Kelly-Walker法的最大优势在于，此项目在实施中出现了较大的变更，相对于传统计划方法，使用Kelly-Walker法更容易更新计划，其工作量仅有最初建立计划的10%，另外，在设计信息只有30%的情况下，能够比较准确的预测劳动力，还有就是能够比较准确的识别关键的采购工作。

1958年，他们进行了第二次试验，此试验所针对的是一个价值2000万美元的化学设备项目，根据Kelly和Walker在1959年发表的论文，此次试验显示的最主要的优点是能够比较容易的包含设计部分的计划。

不过现在人们最常提及的一个试验是他们随后进行的维护设备的试验，在此项目中，他们使用Kelly-Walker法进行分析和计划，使得设备维护时间减少了25%。

1959年，Kelly和Walker共同发表了”CriticalPath Planning and Scheduling” 论文，在这篇长达25页的论文中，Kelly和Walker不仅阐述了关键路径法的基本原理，还提出了资源分配与平衡，费用计划的方法。我们今天所使用的方法的原理，与Kelly和Walker在论文中提出的方法，并没有原则上的不同。

不过随后关键路径法的发展并不是很顺利，杜邦公司开发此项技术的领导层更换之后，不再使用这项技术，而雷明顿兰德公司也认为这项技术没有太大前途。

对于关键路径法的发展起到重要作用的是Mauchly博士和Kelly随后成立的Mauchly合伙公司。在60年代初期，在Kelly的带领下，此公司进行了大量的关键路径法的培训和推广工作。

与此同时，另外一个对关键路径法（CPM）的发展起到重要作用的是美国海军北极星计划开发的计划评审技术（PERT）。在1955年11月17日，美国海军北极星计划成立了一个特别项目管理办公室（SPO），管理其Fleet Ballistic Missile计划，负责人是Admiral Raborn。在1956年和1957年期间，他们研究了各种已经存在的项目管理技术，在大约1957年秋季的时候，他们接触到了杜邦公司开发的计划管理技术，这对他们开发PERT起到了重要的作用。1958年1月份，SPO研究了在计算机上实现计划和控制的可行性，1958年1月27日，SPO正式成立了一个小组开发PERT技术，在大约一年以后，PERT技术成为一种可操作性的技术，计划评审技术（PERT）和关键路径法（CPM）基本上一样，唯一的区别是计划评审技术的每个活动的工期不是确定的，而是包括了悲观值，乐观值和最有可能值三个值。比较有趣的是，1959年，北极星计划的这个特别项目管理办公室（SPO）开了一个招待会，介绍他们的这种新技术，并希望参会者能给出更多的意见，Kelly和Walker在被邀请之列，在会上，他们发现SPO开发的PERT和他们的Kelly-Walker法原理上完全一样，而SPO所说的关键线路（Critical Path），就是他们的Kelly-Walker法中的主链路（Main Chain）。回去之后，他们决定将它们的方法的名称改为关键路径法（Critical Path Method）。

在60年代初期，PERT的发展比较迅速，据统计，到1964年，关于PERT的参考书目和论文达到了1000多种。到1961年，各种基于PERT的类似的方法出现，如PERT/Cost, PERT-RAMPS（Resource Allocation & Multi-Project Schedule），MAPS，SCANS，TOPS，PEP，TRACE，LESS和PAR等。其中PEP法是将甘特图的活动赋以逻辑关系，这是现在的计划软件一般采用的一种图形输出方法。在1962年的时候，时任美国国防部长MacNamara在起草一项法令时，指出计划评审法和关键路径法同时并存的局面容易引起混淆，以后国防部的所有部门一律使用计划评审法（PERT），这在当时对于关键路径法的提倡者是一个重大打击，不过在随后的发展中，关键路径法（CPM）逐渐占了优势，现在真正使用计划评审法的其实已经很少。而且即使是在当时，很多所谓的计划评审法（PERT），其实质其实是关键路径法（CPM）。如美国航空局（NASA）当时使用的NASA-PERT，实际就是关键路径法（CPM）。

无论是关键路径法（CPM）还是计划评审法（PERT），最初使用的表示方法都是箭线法（ADM），在之后很长的一段时间箭线法（ADM）都是人们主要使用的方法，直到70年代以后，前导图（PDM）才开始逐渐流行起来，但是箭线法（ADM）仍然使用极为广泛。在90年代以后，美国Primavera公司开发出其Windows版本的计划管理软件时，只采用前导图（PDM）作为其计算平台，从根本上改变了这一局面，从此以后，前导图（PDM）成了人们主要使用的方法，而箭线图（ADM）则很少使用。

在早期对于前导图（PDM）的发展起到重要作用的是美国斯坦福大学的John W. Fondahl,他是60年代初期的非计算机关键路径法的权威，1961年他发表了一篇题为”A Non-computer Approach to Critical Path Methods for theConstruction Industry”，在这篇论文中，他阐述了前导图系统，并把它作为一种效率比较高的手工绘制关键路径法的方法，因为当时使用计算机运行CPM是非常昂贵的。Fondahl从1958年开始作为斯坦福大学的成员，受美国海军委托为其研究提高生产效率的方法。其中最主要的成果就是这份论文，这份论文当时一共出售了20000份。

在这份论文中，根据习惯使用的流程图方法，Fondahl提出了以节点表示活动以连接线表示活动间的逻辑关系。论文论述了流程图的简易性和使用手算在较少的人力投入下采用关键路径法的可能性，同时论文也论述了费用工期互为反比的问题。斯坦福大学之后继续研究了前导图（PDM）的手工进度更新的问题，并在1964年发表了相关的技术报告。

虽然Fondahl博士极力强调他提出的方法是为了手工计算关键路径法，但是H.B Zachry公司在1962年开始研究将前导图法用于计算机上，1963年3月他们与IBM公司联合进行该项研究，之后形成了IBM的计划软件，名为”Project Control System（PCS）”。该系统还是第一个在计划中引入时间间隔（LAG）的软件。虽然前导图法最初被应用于大型机，但是随后被广泛应用于小型机和个人电脑上的软件，这一趋势使得前导图（PDM）逐渐成为主要使用的方法，到现在，在国外前导图（PDM）基本已经成为唯一在使用的方法，而箭线图（ADM）只有在教学和培训中还有时用到。而发展势头曾一度压过关键路径法（CPM）的计划评审技术（PERT），现在使用的已经很少了。

在美国发展出关键路径法（CPM）和计划评审技术（PERT）的同时，其它一些国家如欧洲和英国等，也曾经开发出一些类似的项目管理技术，但是现在关于这些技术的记载已经很少。

关键路径法（CPM）最初被开发是用于项目管理，不过，在发展过程中，它逐渐在工程项目的合同索赔和纠纷解决上起到重要作用。最早在诉讼中涉及到要求使用关键路径法（CPM）是1972（Appeal of Minmar Builders, Inc, GSBCA No. 3430, 72-2 BOA）年，在此案例中，法庭由于承包商没有使用关键路径法（CPM）而拒绝了承包商的索赔，因为其使用的横道图不能显示具体的活动是否在关键线路上，从而无法判断活动耽误对于整体的影响。之后，关键路径法（CPM）逐渐成为工期延误索赔中必须的做法，并逐渐形成了很多专门的分析方法，现在甚至有很多人专业从事工期延误分析的工作。