关键路径要径法

关键路径法(CriticalPathMethod，CPM)，又称为要径法，是计划项目活动中用到的一种算术方法。

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

中文名

关键路径法

外文名

CriticalPathMethod，CPM

别名

要径法

AOE网

用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE(ActivityOnEdgeNetwork)网。在建筑学中也

称为关键路线。AOE网常用于估算工程完成时间。例如:图1是一个网。其中有9个事件v1，v2，…v9;11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v1表示整个工程开始，v9表示整个工程结束。V5表示，活动a2和a3已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6个时间单位可以完成。

图1

AOE网性质

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

只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。

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

A、从开始顶点v1出发，令ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。Ve(k)=max{ve(j)+dut(<j,k>)}(1.1)j∈T其中T是以顶点vk为尾的所有弧的头顶点的集合(2≤k≤n)。

如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

B、从完成顶点vn出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:

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是关键活动。

表1

关键路径

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

图2

算法分析

C++完整代码

#include<iostream>

#include<cstdio>

#include<string.h>

usingnamespacestd;

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

voidinit()

{

inti,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]++;

}

}

inlinevoidNewq(intv)

{

r++;

queue[r]=v;

}

inlinevoidDel(intv)

{

inti;

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

if(w[v][i])

{

prev[i]–;

if(!prev[i])

Newq(i);

}

}

voidtopo()

{

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

if(!prev[i])

Newq(i);

while(r<n)

{

l++;

Del(queue[l]);

}

}

voidcrucialpath()

{

inti,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;

}

}

voidprint()

{

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

inti=n,k=0;

while(i!=1)

{

k++;

path[k]=i;

}

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

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

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

}

intmain()

{

init();

topo();

crucialpath();

print();

return0;

}

参考资料

1.关键路径法·中国知网

….