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

一个项目可以有多个、并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。最初，关键路径方法只考虑终端元素之间的逻辑依赖关係。关键链方法中增加了资源约束。关键路径方法是由杜邦公司发明的。

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

V_e(k)=max{v_e(j)+dut(<j,k>)} , j ∈ T 。其中T是以顶点v_k为尾的所有弧的头顶点的集合（2 ≤ k ≤ n）。

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

B、从完成顶点出发，令，按逆拓扑有序求其余各顶点的允许的最晚发生时间：

v_l(j)=min{v_l(k)-dut(<j,k>)} ,k ∈ S 。其中 S 是以顶点v_j是头的所有弧的尾顶点集合（1 ≤ j ≤ n-1）。

C、求每一项活动ai（1 ≤ i ≤ m）的最早开始时间e(i)=v_e(j)，最晚开始时间l(i)=v_l(k)-dut(<j,k>) 。

若某条弧满足 e(i)=l(i) ，则它是关键活动。

（1）AOE网

用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如：图1 是一个网。其中有9个事件v₁,v₂,…,v₉；11项活动a₁,a₂,…,a₁₁。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v₁表示整个工程开始，v₉ 表示整个工程结束。V₅表示活动a₂和a₃已经完成，活动a₇和a₈可以开始。与每个活动相联繫的权表示完成该活动所需的时间。如活动a₁需要6个时间单位可以完成。

图1.有向网路

一个AOE网的关键路径可以不止一条。

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

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

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

（4） 事件开始的最早时间v_e(i)；

（5） 事件开始的最晚时间v_l(i)。

（1） 完成整个工程至少需要多少时间；

（2） 哪些活动是影响工程的关键。

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

（1） 输入e条弧<j,k>，建立AOE网的存储结构；

（2） 从源点v₁出发，令v_e(1)=0，求 v_e(j) ,2<=j<=n；

（3） 从汇点v_n出发，令v_l(n)=v_e(n)，求 v_l(i), 1<=i<=n-1；

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

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

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

（2） 只有缩短关键活动的工期才有可能缩短工期；

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

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

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);

}

}

#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;

}