关键路径

关键路径介绍
　　关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。
　　一个项目可以有多个，并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。
　　最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。
　　关键路径方法是由杜邦公司发明的。探寻关键路径

AOE网

　　用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。例如：

图1

图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(<j,k>)} （ 1.1 ） j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。
　　如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

表1

B、从完成顶点 v n 出发，令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 是关键活动。

AOE 网的关键路径

　　

图2

这时从开始顶点到达完成顶点的所有路径都是关键路径。一个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>(即从顶点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[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<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>
　　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;
　　}