关键路径

核心路径介绍

核心路径的工期决定了整个项目的工期。任何核心路径上的终端元素的推迟将直接影响项目的预期完成时间（比如在核心路径上没有浮动时间）。

一个项目可以有多个，并行的核心路径。其他总工期比核心路径的总工期略少的一条并行路径被称为次核心路径。

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

核心路径方法是由杜邦公司发明的。探寻核心路径

AOE网

用顶点表明事件，弧表明活动，弧上的权值表明活动连续的时间的有向图叫AOE（Activity On Edge Network）网。AOE网常用于估算工程完成时间。比如：图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11。每个事件表明在它以前的活动已经完成，在它之后的活动可以开始。如 v1表明整个工程开始，v9 表明整个工程终结。V5表明活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表明完成该活动所需的时间。如活动a1需要6日时间可以完成。

AOE 网具有的性质

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

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

最早发生时间和最晚发生时间的定义

可以采取如下步骤求得核心活动：

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

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

假使得到的拓朴有序序列中顶点的个数差于网中顶点个数n，则表明网中有环，不能求出核心路径，算法终结。B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:

vl(j)=min{vl(k)-dut()} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。

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

l(i)=vl(k)-dut() 若某条弧满足 e(i)=l(i) ，则它是核心活动。

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

AOE 网的核心路径

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

AOE网研究的困难

（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)表明，其连续时间记为dut(),则

e(i)=ve(j)

l(i)=vl(k)-dut() (6_6_1)

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

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

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

T, 2<=j<=n

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

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

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

S, 1<=i<=n-1

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

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

4、求核心路径的算法

(1) 输入e条弧，建立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

else return OK;

}

status CriticalPath(ALGraph G){

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

vl[0..G.vexnum-1]=ve[0..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

}

for(j=0;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

using namespace std;

int n,m,w[1001][1001],pv[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;

pv[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])

{

pv[i]--;

if (!pv[i])

Newq(i);

}

void topo()

{

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

if (!pv[i])

Newq(i);

while (r

{

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;

}