关键路径（AOE网）

关键路径（AOE网）

关键路径

1.概念介绍

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

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

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

上图的关键路径为：( v 0 v_0 v0​， v 2 v_2 v2​， v 3 v_3 v3​， v 4 v_4 v4​， v 7 v_7 v7​， v 8 v_8 v8​， v 9 v_9 v9​)

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

2.关键路径的例子

以下面这个例子引出关键路径算法
下图中的关键路径为：
( v 0 v_0 v0​， v 1 v_1 v1​， v 4 v_4 v4​， v 6 v_6 v6​， v 8 v_8 v8​) 关键路径长度为18
( v 0 v_0 v0​， v 1 v_1 v1​， v 4 v_4 v4​， v 7 v_7 v7​， v 8 v_8 v8​) 关键路径长度为18
关键活动为：
( a 1 a_1 a1​， a 4 a_4 a4​， a 7 a_7 a7​， a 10 a_{10} a10​)
( a 1 a_1 a1​， a 4 a_4 a4​， a 8 a_8 a8​， a 11 a_{11} a11​)

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

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

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

图中 w 0 , 1 w_{0,1} w0,1​ 代表弧< v 0 v_0 v0​， v 1 v_1 v1​>对应的权值

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

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

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

事件（顶点）的发生时间

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

活动 a i a_i ai​=< v j v_j vj​， v k v_k vk​>的最早开始时间 e ( i ) e(i) e(i)
只有事件 v j v_j vj​ 发生了，活动 a i a_i ai​ 才能开始

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

活动 a i a_i ai​=< v j v_j vj​， v k v_k vk​>的最晚开始时间 l ( i ) l(i) l(i)
活动 a i a_i ai​ 的开始时间需保证不延误事件 v k v_k vk​ 的最迟发生时间

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

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

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

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

活动（弧）的开始时间

5.关键路径的算法实现

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

Status CriticalPath(){if(!TopologicalOrder(G,topo))	//调用拓扑排序算法，使拓扑序列保存在toporeturn 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_kwhile(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++)	//初始化数组vlvl[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_kwhile(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的第一邻接点je=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以便下一次循环寻找顶点的下一个邻接点}}
}