关键路径

关键路来自径法(Critical Path Meth步解顺动低od，CPM)，又称为要径法，是计划项目活动中用到的一种算术方法。[1] 对于有效的计划管360百科理而言，关键路径是一个十分重要的工具。与计划评核术(Proj看立务点听答ect Evaluation and Review Techn次剂得维波热质征备ique，PERT)非常类似。要径法所使用的估计作业时间是单一或确定的，而计划评核术则是使用机率性的估计作业时封件报活间。这两种技术经常混合使用，简称CPM/PER笔敌入屋T 。

• 中文名 关键路径法
• 外文名 Critical Path Method，CPM

介绍

　　来自关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素充族家临更的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间(例如在关键路径上没有浮动时间)。 但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。

　　一个项目可以有多个、并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径晚损提话了双末整够秋。

　　最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。

　　关键路径方法是由杜邦公司发明的。

探寻

AOE网

　　用顶点表示事件，弧表示活动，弧上的权值表示360百科活动持续的时间的有向图叫AOE(A己践常速ctivity On Edge Network)网。在建筑学中也称为关键路线。AOE网常用于估算工程硫量愿立乡止变完成时间。例如:图1 是一个网。其中有9个事件v1，v2，…，v9;11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，磁杨弱在七v9 表示整个工程结束。V5表示，活动a2和a3已经完成，活动a7和a8可以开始。己南路叶与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6个时间单位可以完成。

图1

AOE网性质

　　只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。

　　只有在进入某一顶与余品跳顾曲展分皮首已点的各有向边所代表的活动都已经结束，该顶点所代表的事危怕浓夜送绝钟练报利件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入促度过为0的开始顶点和唯一的出度为0的完成顶点。2)

时间的定义

　　可以采取如下步骤求得关键活动:

　　A、从开始顶点 v 1 出发，令 ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。

　　Ve(k)=max{ve(j)+dut(<j,k>)} ( 1.1 ) j ∈ T 其中T造是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n)。

　　如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关切洋尼行儿设键路径，算法结束东尔决脚没半命冷宣边。B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:

表1

若亲降洲能毛　　vl(j)=min{vl(k)-dut(<j,k>)} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1)。

　　C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j);最晚开始时间:

　　l(i)=vl(k)-dut(<j,k>) 若某条弧满足 e(i)=l(i) ，则它是关键活动。

　　对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1,a4,a7,a8,a10,a11 是关键活动。

关键路径

　　这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如前氢风被印赶负至主图7.21的AOE网中有二条关键路径，(v1,v2,v5,v7,v9 ) 和 (v1,v2,v5,v8,v9 )它们的路径长度都是24。如图2所示:

图2

研存果搞附照助扬越也究的问题

　　(1) 完成整个工程至少需要多少时间;

　　(2) 哪些活动是影响工程的关键。

　　1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公肉快校适司在采用关键路径法的一年中，节省了100万美元。

关键路径术语

　　(1) 修元药关键路径:从源点到汇点的路径长度最长的路径叫关键路径。

　　(2) 活动开始的最早时间e(i)

　　(3) 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动。

　　(4) 事件开始的最早时间ve(i)

　　(5) 事件开始的最晚时间vl(i)

顺赶用口病更穿北宽燃　　设活动ai由弧<j,k>;(即从顶点j到k)表示，其持续时间记为dut(<j,k>;)，则

　　e(i)=ve(j)

　　l(i)=vl(k)-dut(<j,k>) (6_6_1)

　　求ve(i)和vl(j)分两步:

　　· 从ve(1)=0开始向前递推

　　ve(j)=Max{ ve(i)+dut(<i,j>) } (6_6_2)

　　<i,j>T,2<=j<=n

　　其中，T是所有以j为弧头的弧的集合。

　　· 从vl(n)=ve(n)开始向后递推

　　vl(i)=Min{ vl(j)-dut(<i,j>) } (6_6_3)

　　<i,j>S,1<=i<=n-1

　　其中，S是所有以i为弧尾的弧的集合。

　　两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。

　　4、 求关键路径的算法

　　(1) 输入e条弧<j,k>;，建立AOE网的存储结构。

　　(2) 从源点v1出发，令ve(1)=0，求 ve(j) 2<=j<=n。

　　(3) 从汇点vn出发，令vl(n)=ve(n)，求 vl(i) 1<=i<=n-1。

　　(4) 根据各顶点的ve和vl值，求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

　　求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。

　　Status ToplogicalSort(ALGraph G,stack &T){

　　FindInDegree(G,indegree);

　　InitStack(S);count=0; ve[0..G.vexnum-1]=0;

　　while(!StackEmpty(S))

　　{ Pop(S,j);Push(T,j); ++count;

　　for(p=G.vertices[j].firstarc;p;p=p->nextarc)

　　{k=p>adjvex;

　　if(--indegree[k]==0) Push(S,k);

　　if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info);

　　}

　　}

　　if(count<G.vexnum) return ERROR;

　　else return OK;

　　}

　　status CriticalPath(ALGraph G){

　　if(!ToplogicalOrder(G,T)) return ERROR;

　　vl[0..G.vexnum-1]=ve[G.vexnum-1];

　　while(!StackEmpty(T))

　　for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)

　　{k=p->adjvex; dut=*(p->info);

　　if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;

　　}

　　for(j=0;j<G.vexnum;++j)

　　for(p=G.vertices[j].firstarc;p;p=p->nextarc)

　　{k=p>adjvex; dut=*(p->info);

　　ee=ve[j]; el=vl[k];

　　tag=(ee==el)?'*':'';

　　printf(j,kdut,ee,el,tag);

　　}

　　}

算法分析

　　(1) 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径;

　　(2) 只有缩短关键活动的工期才有可能缩短工期;

　　(3) 若一个关键活动不在所有的关键路径上，减少它并不能减少工期;

　　(4) 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

C++完整代码

　　#include <iostream>

　　#include <cstdio>

　　#include<string.h>

　　using namespace std;

　　int n,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];

　　void init()

　　{

　　int i,a,b,c;

　　scanf("%d%d",&n,&m);

　　for (i=1;i<=m;i++)

　　{

　　scanf("%d%d%d",&a,&b,&c);

　　w[a][b]=c;

　　prev[b]++;

　　}

　　}

　　inline void Newq(int v)

　　{

　　r++;

　　queue[r]=v;

　　}

　　inline void Del(int v)

　　{

　　int i;

　　for (i=1;i<=n;i++)

　　if (w[v][i])

　　{

　　prev[i]--;

　　if (!prev[i])

　　Newq(i);

　　}

　　}

　　void topo()

　　{

　　for (int i=1;i<=n;i++)

　　if (!prev[i])

　　Newq(i);

　　while (r<n)

　　{

　　l++;

　　Del(queue[l]);

　　}

　　}

　　void crucialpath()

　　{

　　int i,j;

　　memset(Time,0,sizeof(Time));

　　for (i=1;i<=n;i++)

　　for (j=1;j<=n;j++)

　　if ((w[j][queue[i]]) && (Time[j]+w[j][queue[i]]>Time[queue[i]]))

　　{

　　Time[queue[i]]=Time[j]+w[j][queue[i]];

　　Pos[queue[i]]=j;

　　}

　　}

　　void print()

　　{

　　printf("%d\n",Time[n]);

　　int i=n,k=0;

　　while (i!=1)

　　{

　　k++;

　　path[k]=i;

　　}

　　for (i=k;i>1;i--)

　　printf("%d ",path[i]);

　　printf("%d\n",path[1]);

　　}

　　int main()

　　{

　　init();

　　topo();

　　crucialpath();

　　print();

　　return 0;

　　}