数据结构与算法-第六章 图的关键路径问题

关键路径–用AOE网表示工程计划

把工程计划表示为边表示活动的网络,即AOE网,用顶点表示事件,弧表示活动,弧的权重表示活动持续时间.
事件表示在它之前的活动已经完成,在它之后的活动可以开始.
那么怎么压缩工程计划,能让总的耗时最少呢?

对于AOE网,我们关系的两个问题

1. 完成整项工程至少需要多少时间?
2. 哪些活动是影响工程进度的关键?

这些问题都能归结为关键路径问题------路径长度最长的路径

路径长度------路径上各活动持续时间之和

如何确定关键路径------需要定义4个描述量

ve(vj)------表示事件的顶点vj的最早发生时间;
vl(vj)------表示事件的顶点vj的最迟发生时间;
e(i)--------表示活动的边ai的最早开始时间;
l(i)--------表示活动的边ai的最迟开始时间;
1
2
3
4

则l(i)-e(i)------表示完成活动ai的时间余量
关键活动------关键路径上的活动,即l(i) == e(i)(即l(i)-e(i) = 0)的活动

如何找l(i) == e(i)的关键活动?

设活动ai用弧<j,k>表示,其持续时间记为W(j,k)
	则有:	(1) e(i) = ve(j)
		  	(2) l(i) = vl(k) - W(j,k) 
	如何求ve(j)和vl(j)?
		1. 从ve(1) = 0 开始向前递推
			ve(j) = MAX{ve(i)+W(i,j)},<i,j>∈T,2<=j<=n
			其中T是所有以j为头的弧的集合;
		2. 从vl(n) = ve(n)开始向后递推
			vl(i) = Min{vl(j) - W(i,j)}, <i,j>∈S,1<=i<=n-1
			其中S是所有以i为尾的弧的集合;
1
2
3
4
5
6
7
8
9
10