2025年数据结构 - 手工求解关键路径

大家好，我是讯享网，很高兴认识大家。

快速方法：

数据结构—图，一分钟求解关键路径！_哔哩哔哩_bilibili

从前往后相加取最大，划掉不需要的路径。

详细步骤做法：

节点最早开始时间：正着找，相加，取大值

节点最晚开始时间：反着找，相减，取小值

边最早开始时间：从谁发出的最早开始时间

边最晚开始时间：被指向的最晚开始时间减去权值

这里先回顾一下几个概念：

AOE网是活动在边上的网（Activity On Edge network，AOE）的英文简称。

AOE网是用有向图来表示的，在有向图中，边表示活动，边具有权值，边的权值代表了活动的持续时间。顶点表示事件，事件是图中新活动开始或者旧活动结束的标识。

与AOV网相同的是，AOE网也是有向无环图，不同的是在AOV网中顶点表示活动，边无权值，边代表活动之间的先后关系。

对于一个表示工程的AOE网，只存在一个入度为0的顶点，成为源点，表示整个工程的开始；也只有一个出度为0的顶点，称为汇点，表示整个工程的结束。

在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径成为关键路径。

关键路径所代表的时间就是完成整个工期的最短时间。关键路径上的活动（边）称为关键活动。

设ve(k)代表事件（顶点）k的最早发生时间，即从源点到顶点k的路径中的最长者，

即ve(k)=max{ve(j)+<j,k>}，其中j为k的前驱事件，且j可能有多个。

初始时，将源点事件的最早发生时间ve(0)设置为0。

设vl(k)代表事件（顶点）k的最晚发生时间，即在不推迟整个工程完成的前提下，

事件k最迟必须发生的时间，即vl(k)=min{vl(j)-<k,j>}，其中j为k的后继事件，j可能有多个。

对于汇点时间来说，它的最早发生时间是整个工程的结束时间，因此他的最早发生时间也是最迟发生时间，即初始时将汇点事件的最晚发生时间vl(n)设置为ve(n)。

设e(ak)代表当前活动（边）ak的最早发生时间，由于事件代表一个新活动的开始或一个旧活动的结束，因此事件的最早发生时间就是有这个事件所发出的活动的最早时间。

即若存在边ak1：<i,j>，ak2：<k,j>，则e(ak1)=e(ak2)=ve(i)。

设l(ak)代表当前活动（边）ak的最晚发生时间，由于图中事件的最迟发生时间代表了以它为结束点的活动的最迟结束时间，因此用时间的最迟发生时间减去以它为结束点的活动的持续时间，就得到活动的最迟发生时间。

即若存在边ak：<i,j>，权值为w，则l(ak)=vl(j)-w。

对于每个活动（顶点），如果活动的最早发生时间和最晚发生时间相同，则该活动就是关键活动。活动剩余时间等于活动的最晚发生时间减去活动的最早发生时间，剩余时间反映了该活动完成的一种松弛度。关键活动的活动剩余时间为0，这也体现了关键活动在整个工程中的重要性，关键活动没有缓期执行的余地。

而由关键活动（顶点）组成的路径就是关键路径。

在草稿纸上对图进行改造，将顶点代表的事件用圆形表示，一份为二，表示事件最早发生时间和事件最迟发生时间；将边代表的活动用矩形表示，同样一份为二，表示活动最早开始时间和最迟开始时间。