关键路径（AOE网）_构造aoe网

关键路径

1.概念介绍

主要解决工程完成需要的最短时间问题
AOE是在AOV基础上概念，即将工程的工序进行拓扑排列后加入活动持续时间

下图中AOE网中，弧上的2代表制造外壳这个活动的持续时间，顶点(外壳完成)是这个活动结束的标志事件。
下面这些活动是可以同时进行的

AOE网：边代表活动，边的权值代表活动的持续时间，顶点代表事件
源点：工程的开始
汇点：工程的结束
顶点$V_0，V_1\dots \dots$表示事件
弧$<V_0,V_1>$，$<V_0,V_2>\dots \dots$表示活动，用$a_0$，$a_1$表示，权值代表活动持续时间
路径长度：路径上各个活动所持续的时间之和（权值大小）
关键路径：从源点到汇点具有最大长度的路径（耗时最长）
关键活动：关键路径上的活动（弧）

上图的关键路径为：($v_0$，$v_2$，$v_3$，$v_4$，$v_7$，$v_8$，$v_9$)

采用邻接表作为有向图的存储结构

2.关键路径的例子

以下面这个例子引出关键路径算法
下图中的关键路径为：
($v_0$，$v_1$，$v_4$，$v_6$，$v_8$) 关键路径长度为18
($v_0$，$v_1$，$v_4$，$v_7$，$v_8$) 关键路径长度为18
关键活动为：
($a_1$，$a_4$，$a_7$，$a_{10}$)
($a_1$，$a_4$，$a_8$，$a_{11}$)

3.事件(顶点)的发生时间

事件（顶点）$v_i$ 的最早发生时间 $ve(i)$
$ve(i)$ 是从源点到 $v_i$ 的最长路径长度

例如：
事件$v_2$代表着活动$a_2$的结束，同时也代表着活动$a_5$的开始，相当于一个标志
活动$a_2$持续的时间为4，该活动结束的标志是事件$v_2$的发生，活动$a_2$结束后紧接着事件$v_2$发生，所以事件$v_2$的最早发生时间是$ve(v_2)=4$

图中 $w_{0,1}$ 代表弧<$v_0$，$v_1$>对应的权值

事件 $v_i$ 的最迟发生时间 $vl(i)$
$v_i$的发生不得延误$v_i$的每一后继事件的最迟发生时间

例如：
整个工程完成需要18分钟，要给活动 $a_{11}$ 留出4分钟的时间，活动 $a_{11}$ 开始的标志是事件 $v_7$ 的发生，即事件 $v_7$ 的最迟发生时间 $vl(v_7)=18-4=14$

求出 $ve(i)$ 后，根据逆拓扑序列从汇点开始向源点递推，求 $vl(i)$

事件（顶点）的发生时间

4.活动(弧)的发生时间

活动 $a_i$=<$v_j$，$v_k$>的最早开始时间 $e(i)$
只有事件 $v_j$ 发生了，活动 $a_i$ 才能开始

例如：
活动 $a_4$ 在活动 $a_1$完成后即可开始，所以活动 $a_4$的最早开始时间 $e(a_4)=6$

活动 $a_i$=<$v_j$，$v_k$>的最晚开始时间 $l(i)$
活动 $a_i$ 的开始时间需保证不延误事件 $v_k$ 的最迟发生时间

例如：
整个工程完成需要 18 分钟，给活动 $a_{11}$ 预留最后的 4 分钟，活动 $a_8$ 持续时间需要 7 分钟，所以活动 $a_8$ 最晚开始时间 $l(a_8)=18-4-7=7$分钟，活动 $a_8$ 最晚要在第 7 分钟的时候开始

一个活动 $a_i$ 的最迟开始时间 $l(i)$ 和其最早开始时间 $e(i)$ 的差值 $l(i)-e(i)$ 是该活动完成的时间余量

关键活动
$l(i)-e(i)=0$，即 $l(i)=e(i)$ 时的活动 $a_i$ 是关键活动。当活动时间余量为0时，说明该活动必须如期完成，不可拖延

非关键活动
$l(i)-e(i)=Constant$ 的值是该工程的期限余量，在此范围内的适度延误不会影响整个工程的工期。表示如果完成整个工程所需的总时间不变的情况下，活动 $a_i$ 可以拖延的时间

活动（弧）的开始时间

5.关键路径的算法实现

G为邻接表存储的有向网，输出G的各项关键活动

Status CriticalPath(){
	if(!TopologicalOrder(G,topo))	//调用拓扑排序算法，使拓扑序列保存在topo
		return ERROR;	//调用失败
	n=G.vexnum;	//顶点个数
	for(i=0; i<n; i++)	//初始化事件(顶点)的最早发生时刻
		ve[i]=0;
//按拓扑排序求每个事件(顶点)的最早发生时刻
	for(i=0; i<n; i++){
		k=topo[i];	//拓扑序列存储的是按工序排好的事件(顶点)的下标
		p=G.vertices[k].firstarc;	//指向顶点V_i的第一邻接点V_k
		while(p != NULL){	//所指的第一邻接点非空
			j = p->adjvex;	//第一邻接点V_k的下标
			if(ve[j] < ve[k]+p->weight)	//ve[j]是从源点到下标为j的当前路径长度
				ve[j] = ve[k]+p->weight;//更新ve[j]后变为最长的路径长度
			p=p->nextarc;	//重命名p->nextarc为p以便下一次循环寻找顶点的下一个邻接点
		}
	}
	for(i=0; i<n; i++)	//初始化数组vl
		vl[i]=ve[n-1];  //下标从0开始，共n个顶点，所以最后一个顶点下标应该是n-1
//按逆拓扑排序求每个事件(顶点)的最迟发生时间
	for(i=n-1; i>=0; i--){	//逆拓扑序列
		k=topo[i];
		p=G.vertices[k].firstarc;  //指向顶点V_i的第一邻接点V_k
		while(p != NULL){
			j=p->adjvex;	//第一邻接点V_k的下标
			if(vl[k] > vl[j]-p->weight) //vl[k]是从汇点到下标为k的当前路径长度
				vl[k] = vl[j]-p->weight; //更新顶点k的最迟发生时刻vl[k]
			p=p->nextarc;	//重命名p->nextarc为p以便下一次循环寻找顶点的下一个邻接点
		}
	}
//判断每一个活动(弧)是否为关键活动
	for(i=0; i<n; i++){
		p=G.vertices[i].firstarc;
		while(p != NULL){
			j=p->adjvex; //顶点i的第一邻接点j
			e=ve[i];	//顶点i的最早发生时刻
			l=vl[j]-p->weight;	//顶点j的最迟发生时刻
			if(e==l) //工程的期限余量为0，意味着不可拖延，所以为关键活动
				cout << G.vertices[i].data << G.vertices[j].data;
			p=p->nextarc; //重命名p->nextarc为p以便下一次循环寻找顶点的下一个邻接点
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43