【数据结构】有向无环图（AOE-网）的关键路径（C语言）_aoe网的关键路径

1. 基本概念

把用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间的有向无环图称为边表示活动的网，简称AOE-网。
在AOE-网中存在唯一的、入度为0的顶点，称为源点；存在唯一的、出度为0的顶点，称为汇点。从源点到汇点的最长路径长度即为完成整个工程任务所需的时间，该路径称为关键路径。关键路径上的活动称为关键活动。这些活动中的任意一项活动未能按期完成，则整个工程的完成时间就要推迟；相反如果能加快关键活动的进度，则整个工程可以提前完成。
例如，上图所示的AOE-网中，共有v0,v1,v2,…,v8这9个事件。v0为源点，v8为汇点。v0到v8的关键路径（最长路径）有两条：v0,v1,v4,v6,v8或v0,v1,v4,v7,v8，长度均为18。关键活动为a1,a4,a7,a10或a1,a4,a8,a11。关键活动a1计划6天完成，若a1提前两天完成，则整个工程也可以提前两天完成。

几个基本定义：
拓扑排序见：https://blog.csdn.net/weixin_51450101/article/details/123018532?spm=1001.2014.3001.5501
① 事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径长度。
求ve(i)可以从源点开始，按拓扑顺序向汇点逆推：
ve(0)=0；
ve(i)=Max{ve(k)+dut(<k,i>)}，dut(<k,i>)表示与弧<k,i>对应活动的持续时间
② 时间vi的最晚发生时间vl(i)：在保证汇点按其最早发生时间发生的这一前提下，求事件vi的最晚发生时间。即在求出ve(i)的基础上，从汇点开始，按逆拓扑顺序向源点递推，求出vl(i)：
vl(n-1)=ve(n-1)；
vl(i)=Min{vl(k)-dut(<i,k>)}，dut(<i,k>)表示与弧<i,k>对应活动的持续时间
③ 活动ai的最早开始时间e(i)：如果活动ai对应的弧为<j,k>，则e(i)等于从源点到顶点 j 的最长路径长度，即e(i)=ve(j)。
④ 活动ai的最晚开始时间l(i)：如果活动ai对应的弧为<j,k>，其持续时间是dut(<j,k>)，则有l(i)=vl(k)-dut(<j,k>)。
⑤ 活动ai的松弛时间（时间余量）：ai的最晚开始时间与最早开始时间之差，即l(i)-e(i)。显然松弛时间为0的活动为关键活动。

2. 求关键路径的基本过程及计算步骤

基本过程：
① 对图中顶点进行拓扑排序，在排序过程中按逆拓扑序列求出每个事件的最早发生时间ve(i)；
② 按逆拓扑序列求每个事件的最晚发生时间vl(i)；
③ 求出每个活动ai的最早开始时间ei(i)和最晚开始时间l(i)；
④ 找出e(i)=l(i)的活动ai即为关键活动。
计算步骤：
以上图所示AOE-网为例：
① 计算各顶点的最早开始时间
ve(0) = 0
ve(1) = Max {ve(0) + dut(<0,1>)} = 6
ve(2) = Max {ve(0) + dut(<0,2>)} = 4
ve(3) = Max {ve(0) + dut(<0,3>)} = 5
ve(4) = Max {ve(1) + dut(<1,4>)，ve(2) + dut(<2,4>)} = 7
ve(5) = Max {ve(3) + dut(< 3,5>)} = 7
ve(6) = Max {ve(4) + dut(<4,6>)} = 16
ve(7) = Max {ve(4) + dut(<4,7>)，ve(5) + dut(<5,7>)} = 14
ve(8) = Max {ve(6) + dut(<6,8>)，ve(7) + dut(<7,8>)} = 18
② 计算各顶点的最迟开始时间
vl(8) = ve(8) = 18
vl(7) = Min {vl(8) - dut<7,8>} = 14
vl(6) = Min {vl(8) - dut<6,8>} = 16
vl(5) = Min {vl(7) - dut<5,7>} = 10
vl(4) = Min {vl(7) - dut<4,7>，vl(6) - dut(<4,6>)} = 7
vl(3) = Min {vl(5) - dut<3,5>} = 8
vl(2) = Min {vl(4) - dut<2,4>} = 6
vl(1) = Min {vl(4) - dut<1,4>} = 6
vl(0) = Min {vl(3) - dut(<0,3>)，vl(2) - dut<0,2>，vl(1) - dut(<0,1>)} = 0
③ 计算各活动的最早开始时间
e(a1) = ve(0) = 0
e(a2) = ve(0) = 0
e(a3) = ve(0) = 0
e(a4) = ve(1) = 6
e(a5) = ve(2) = 4
e(a6) = ve(3) = 5
e(a7) = ve(4) = 7
e(a8) = ve(4) = 7
e(a9) = ve(5) = 7
e(a10) = ve(6) = 16
e(a11) = ve(7) = 14
④ 计算各活动的最迟开始时间
l(a11) = vl(8) - dut(<7,8>) = 14
l(a10) = vl(8) - dut(<6,8>) = 16
l(a9) = vl(7) - dut(<5,7>) = 10
l(a8) = vl(7) - dut(<4,7>) = 7
l(a7) =vl(6) - dut(<4,6>) = 7
l(a6) =vl(5) - dut(< 3,5>) = 8
l(a5) =vl(4) - dut(<2,4>) = 6
l(a4) =vl(4) - dut(<1,4>) = 6
l(a3) =vl(3) - dut(<0,3>) = 3
l(a2) =vl(2) - dut(<0,2>) = 2
l(a1) =vl(1) - dut(<0,1>) = 0
⑤ 计算活动ai的松弛时间
l(a1) - e(a1) = 0
l(a2) - e(a2) = 2
l(a3) - e(a3) = 3
l(a4) - e(a4) = 0
l(a5) - e(a5) = 2
l(a6) - e(a6) = 3
l(a7) - e(a7) = 0
l(a8) - e(a8) = 0
l(a9) - e(a9) = 3
l(a10) - e(a10) = 0
l(a11) - e(a11) = 0
松弛时间为0的活动即为关键活动，由计算结果得关键活动为：a1,a4,a7,a8,a10,a11
关键路径为：v0,v1,v4,v6,v8 或 v0,v1,v4,v7,v8

3. 实现代码及运行结果

求逆拓扑序列及事件最早发生时间ve(i)

int indegree[MAX_VERTEX_NUM];			//存放各顶点入度数
int ve[MAX_VERTEX_NUM];					//各顶点的最早发生时间
void FindID(AdjList G);					//求各顶点入度算法

/*拓扑排序，求逆拓扑序列及事件最早发生时间ve(i)*/
int TopoSort(AdjList G, SeqStack* T) {
   	//栈T用于生成逆拓扑序列
	int i, k, count = 0;
	SeqStack S;							//栈S用于存放入度为0的顶点
	ArcNode* p;
	FindID(G);							//求各顶点入度
	InitStack(T);						//初始化栈T
	InitStack(&S);						//初始化栈S
	for (i = 0; i < G.vexnum; i++) {
   
		if (indegree[i] == 0)
			Push(&S, i);				//将入度为0的顶点入栈S
	}
	for (i = 0; i < G.vexnum; i++)
		ve[i] = 0;						//初始化最早发生时间
	while (!IsEmpty(&S)) {
   
		i = S.elem[S.top];
		Pop(&S);
		count++;
		Push(T, i);						//按拓扑顺序进入栈T
		p = G.vertex[i].firstarc;
		while (p != NULL) {
   
			k = p->adjvex;
			indegree[k]--;				//i号顶点的每个邻接点的入度减1
			if (indegree[k]
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