关键路径
关键路径
1、 AOE网
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。
2、 AOE网研究的问题
（1） 完成整个工程至少需要多少时间；
（2） 哪些活动是影响工程的关键。
1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。
3、 关键路径的几个术语
（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);
}
}
6、 求关键路径的算法分析
（1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；
（2） 只有缩短关键活动的工期才有可能缩短工期；
（3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期；
（4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。