关键路径¶
前言¶
AOE网¶
在带权有向图中， 以顶点表示 事件 ，以 有向边 表示 活动 ，以 边上的权值 表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 \(AOE\) 网
\(AOE\) 网和 \(AOV\) 网都是有向无环图，不同之处在于， \(AOE\) 网的边有权值，而 \(AOV\) 网无权值，仅表示顶点之间的前后关系， \(AOE\) 网的两个性质如下：
- ①只有在 某顶点所代表的事件发生后 ，从该顶点出发的各有向边所代表的活动才能开始
- ②只有在进入某顶点的各 有向边 所代表的 活动 都已 结束 时，该顶点所代表的事件才能发生。
注意 - 在 \(AOE\) 网中，有些活动是可以并行进行的 - 从源点到汇点的有向路径可能有多条， 并且这些 路径长度 可能不同，因此从源点到汇点中 最大路径长度（即最大边权和） 的路径称为 关键路径 ，关键路径上的活动称为 关键活动 ，显然这个关键路径可能有多条 - 只有 所有路径的活动 都完成，整个工程才算结束
事件\(V_k\) 的最早发生时间 \(Ve(K)\)¶
它是指从源点 \(V_1\) 到顶点 \(V_k\) 的最长路径长度。事件 \(V_k\) 的最早发生时间决定了所有从 \(V_k\) 开始的 活动能够开工的 最早时间 。 可用下面的边推公式来计算： - \(Ve(源点)=0\) - \(Ve(k) = Max{Ve(j)+Weight(V_j,V_k)}\) ，其中的 \(V_k\) 为 \(V_j\) 的任意后继结点， \(Weight(V_j,V_k)\) 表示 \(<V_j,V_k>\) 边上的权值
简单理解一下，假设我们当前走到了点 \(j\) ，然后我们将点 \(j\) 的所有出度点 \(k\) 的 \(Ve(k)\) 值和当前 \(j\) 点的 \(Ve(j)\)加边权 \(<j,k>\) 进行比较，如果后者大就更新为后者（就是尽可能让 \(Ve(k)\) 更大），看到这个我们很自然想起了拓扑排序，我们可以再拓扑排序的基础上进行计算
这里说一下为什么称为 最早发生时间 ，毕竟刚接触怎么看都是 “最迟” ，想象一下，这个 \(AOE\) 网是从源点出发，可能会存在多个活动并行进行的情况，但目的都是到达汇点，那么在这个过程中，可能通过某些活动（弧）早到，有的活动（弧）晚到，其中最晚到的活动（弧）就是关键活动，对于那些能 “早到” 的路径来说就会存在两个情况，是先完成活动再等待那个所谓的关键活动完成，还是先等待关键活动，然后再完成这个活动，这里先完成当前的活动就是最早发生时间，而等待后再来完成就是一个活动开始最迟时间，很显然 在关键路径上的最早发生时间和最迟发生时间是一样的
事件\(V_k\) 的最迟发生事件 \(Vl(K)\)¶
它是指在不推迟整个工程完成的前提下， 即保证它的后继事件 \(V_j\) 在其最迟发生时间 \(Vl(j)\) 能够 发生时，该事件最迟必须发生的时间 。 可用下面的递推公式来计算： - \(Vl(汇点)=Ve(汇点)\) - \(Vl(k) = Min{Vl(j) + Weight(V_k,V_j)}\) ，其中点 \(V_k\) 为 \(V_j\) 的任意前驱结点， \(Weight(V_k,V_j)\) 表示 \(<V_k,V_j>\) 边上的权值
这里其实和上面流程其实是类似的，只不过需要从汇点出发一直到源点，那么这个很显然就是一个逆拓扑排序的操作，然后不断地尽可能最小化 \(Vl(k)\) 的值，当然对于关键路径上的活动的 \(Vl(k)\) 和 \(Ve(k)\) 是相同的
活动 \(a_i\) 的最早开始时间 \(e(i)\)¶
它是指该活动弧的起点所表示的事件的最早发生时间。若边 \(＜V_k, V_j>\) 表示活动 \(a_i\) ，则有 \(e(i) =Ve(k)\)
活动 \(a_i\) 的最迟开始时间 \(l(i)\)¶
它是指该活动弧的终点所表示 事件的最迟发生时间 与该 活动所需时间 之差。若边 \(＜V_k，V_j＞\) 表示活动 \(a_i\) ，则有 \(l(i) = vl(j) - Weight(V_k,V_j)\)
活动的差额d¶
它是指该活动完成的时间余量，即在 不增加完成整个工程所需总时间 的情况下，活动 \(a_i\) 可以拖延的时间，若一个活动的时间余量为 \(0\) 则说明这个活动必须要如期完成，否则会延长整个工期，换句话说就是 关键活动 \(d(i) = l(i) - e(i)\)
原理¶
求解关键路径的算法步骤大体为五步：
- ①从源点出友，令 \(Ve(源点) = 0\)，按拓扑有序求其余顶点的最早发生时间 \(Ve(i)\)
- ②从汇点出友，令 \(Vi(汇点) = Ve(汇点)\) ， 按逆拓拓扑有序求其余顶点的最迟发生时间 \(Vl(i)\)
- ③根据各顶点的 \(ve(i)\) 值求所有孤的最早开始时间 \(e(i)\)
- ④根据各顶点的 \(vl(i)\) 值求所有孤的最早开始时间 \(l(i)\)
- ⑤求 \(AOE\) 网 中所有活动的差额 \(d()\)，找出所有 \(d() = 0\) 的活动构成关键路径（可能不唯一）
举例：
注意： 因为 \(AOE\) 网中的关键路径可能不唯一，提高某一个活动的效率可能并不能加快整体工程的效率 关键路径的难点在于理解事件的 最早和最迟时间
代码实现¶
思路较为简单，且未碰到编程类的题目，博主这里就不做实现了，可以参考另一位大佬的实现代码： 博客链接：https://blog.csdn.net/weixin_42638946/article/details/120154312
/*
输出关键路径
input:
9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4
output:
1 2 5 8 9
1 2 5 7 9
*/
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010, M = 100010;
int n, m;
int hs[N], ht[N], e[M], w[M], ne[M], idx; // 顶点表示事件，边表示活动
int ve[N], vl[N]; // 事件允许的最早发生时间, 事件允许的最晚发生时间
// int ee[M], el[M]; // 活动的最早发生时间, 活动的最晚发生时间
int d[N]; // 每个点的入度
int q[N]; // 拓扑排序数组
vector<int> path;
vector<vector<int>> res;
void add(int h[], int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void topsort() {
int hh = 0, tt = 0;
q[0] = 1;
while (hh <= tt) {
int t = q[hh++];
for (int i = hs[t]; ~i; i = ne[i]) {
int j = e[i];
if (--d[j] == 0)
q[++tt] = j;
}
}
}
void critical_path() {
topsort();
// 求解事件允许的最早发生时间
ve[1] = 0;
for (int k = 0; k < n; k++) {
int ver = q[k];
for (int i = hs[ver]; i != -1; i = ne[i]) {
int j = e[i];
ve[j] = max(ve[j], ve[ver] + w[i]);
}
}
// 求解事件允许的最晚发生时间
memset(vl, 0x3f, sizeof vl);
vl[n] = ve[n];
for (int k = n - 1; k >= 0; k--) {
int ver = q[k];
for (int i = ht[ver]; i != -1; i = ne[i]) {
int j = e[i];
vl[j] = min(vl[j], vl[ver] - w[i]);
}
}
}
void dfs(int u) {
path.push_back(u);
if (hs[u] == -1) {
res.push_back(path);
}
for (int i = hs[u]; ~i; i = ne[i]) {
int j = e[i];
if (vl[j] - ve[j] == 0)
dfs(j);
}
path.pop_back();
}
int main() {
cin >> n >> m;
memset(hs, -1, sizeof hs);
memset(ht, -1, sizeof ht);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(hs, a, b, c);
add(ht, b, a, c);
d[b]++;
}
// 输入满足1号点是源点，n号点是汇点
critical_path();
dfs(1);
for (auto &t : res) {
for (int i = 0; i < t.size(); i++)
cout << t[i] << ' ';
cout << endl;
}
return 0;
}
这个 \(AOE\) 图大概长这样：
