关键路径：AOE网

TryHardToBeAlive · 2023-03-21 20:44:11 · 个人记录

关键路径：AOE网（Activity On Edge Network）

更多详解见 《算法训练营》

~~我们的信竞教练：关键路径的题怎么这么难找...~~

一，关键路径定义

从源点（开始点，即入度为0的点）到汇点（即出度为0的点）之间的最长的一条路径，称这条最长的路径为关键路径。

二，关键路径的相关定义与概念

0、“事件”可理解成有向图的顶点，“活动”可理解为有向图的边。

1、ve：事件可能发生的最早时间。

2、vl：在保证不耽误它的下一个事件的前提下，事件v所允许发生的最晚时刻。

3、e：活动最早可以开始时间。可以以“a_i：<v_i,v_k>”形式出现。

4、l：活动最晚必须开始时间。可以以“a_i：<v_i,v_k>”形式出现。

5、关键活动：即e[k]=l[k]的活动。

6、时间余量 l-e ：完成活动的时间余量，即在不延误工期情况下，活动可以延迟的时间。如l[k]-e[k]表示在不延误工期情况下活动a_k可以延迟的时间。

三，关键路径的求法

1、公式：

有关事件（点）：

ve[k]=max(ve[j]+len<v_j,v_k>)

vl[k]=min(vl[j]-len<v_k,v_j>)

有关活动（边）：

e[i]=ve[k]

l[i]=vl[j]-len<v_k,v_j>

2、解释：

注意：所有的最早发生时间与最晚发生时间都是根据拓扑排序正反两次排序来计算的。

First:

对于第一个公式 ve[k]=max(ve[j]+len<v_j,v_k>) ，其含义是找到找到所有点 k 能一步返回的点（即点k入边的起点，前驱点），记它（们）为点 j ，取点 j 的事件最早发生时间加上点 j 到点 k 的边的权值，取这些和中的最大值。

好的问题来了，公式是怎么来的？

公式怎么来的很容易理解。一个事件的最早发生事件其实就是它的前驱点最早发生时间加上前驱点到这个点的距离（边权）。问题是，一个点可能会有很多前驱点，这就引出了下一个问题：

为什么要取最大值呢？

其实，取最大值的原因可以通过一个简单例子来理解。小明的妈妈在开饭前要做好蒸肉饼和炒青菜两道菜，这两道菜可以同时做，但做蒸肉饼要15分钟，而炒青菜只需10分钟，问何时开饭。很显然，做完炒青菜后必须要等蒸肉饼做完才能开饭，所以应该取两道菜所花时间的较大值，也就是例子中花费时间更长的蒸肉饼所花的时间15分钟。在公式中也是这样。

Second:

对于第二个公式 vl[k]=min(vl[j]-len<v_k,v_j>) ，其含义是找到所有点 k 能一步到达的点（即点k出边到达的点，后继点），记它（们）为点 j ，计算点 j 的事件最晚发生时间减去点 k 到点 j 的边的权值，取这些和中的最小值。

跟上面类似的问题，这个公式是怎么来的呢？这里又为什么要取最小值呢？

让我们看回事件发生最晚时间的定义：

在保证不耽误它的下一个事件的前提下，事件v所允许发生的最晚时刻。

正如定义中所述，事件发生的最晚时间必须不耽搁它的下一个事件，也就是这个点的最晚发生时间与这个点到它所有继点分别的和都不得大于其对应继点的最晚发生时间。显然，一个点的最晚发生时间就与它的继点的最晚发生时间有关。至于为什么是最小值，还是举做饭的例子。已知吃完饭（尚不知最晚发生时间）后，还要洗碗和唱歌（可以同时做），洗碗最晚能 8:30 做，而唱歌最晚能 9:00 做。从吃完饭到开始洗碗需要5分钟准备时间，而唱歌不用准备时间，问最晚何时吃完饭。很明显，这个时间既要满足加上洗碗准备时间不大于洗碗最晚的发生时间，又要满足加上唱歌准备时间（这里比较特殊，不需要准备时间）不大于唱歌最晚发生时间。所以有时要同时满足多个要求，这就跟不等式差不多：一个数要同时小于几个数，最后当然就应是小于几个数中的最小者了。公式亦是如此。

注意：在进行操作之前，我们要先设定汇点的事件最晚发生时间为它的最早发生时间，否则无法操作。

四，算法实现

终于来到这个期待已久的环节了，废话不多说，直接贴代码（还带了测试数据）：

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 10010, maxe = 50010;
int n, m, cnt;
int head[maxn]; //链式前向星头
int in[maxn], topo[maxn]; //入度,拓扑序列
int ve[maxn]; //事件vi的最早发生时间
int vl[maxn]; //事件vi的最迟发生时间
stack<int>s;
struct node {
    int to, next, w;
} e[maxe];

void add(int u, int v, int w) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
    e[cnt++].w = w;
}

bool TopoSort() { //拓扑排序
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (in[i] == 0)
            s.push(i);
    while (!s.empty()) {
        int u = s.top();
        s.pop();
        topo[cnt++] = u;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (--in[v] == 0)
                s.push(v);
        }
    }
    if (cnt < n) return 0; //该有向图有回路
    return 1;
}

bool CriticalPath() { //关键路径
    if (TopoSort()) {
        cout << "拓扑序列为：" << endl;
        for (int i = 0; i < n; i++) //输出拓扑序列
            cout << topo[i] << "\t";
        cout << endl;
    } else {
        cout << "该图有环，无拓扑序列！" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) //初始化最早发生时间为0
        ve[i] = 0;
    //按拓扑次序求每个事件的最早发生时间
    for (int j = 0; j < n; j++) {
        int u = topo[j]; //取得拓扑序列中的顶点
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (ve[v] < ve[u] + w)
                ve[v] = ve[u] + w;
        }
    }
    for (int i = 0; i < n; i++) //初始化每个事件的最迟发生时间为ve[n]
        vl[i] = ve[n - 1];
    for (int j = n - 1; j >= 0; j--) { //按逆拓扑序求每个事件的最迟发生时间
        int u = topo[j]; //取得拓扑序列中的顶点
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (vl[u] > vl[v] - w)
                vl[u] = vl[v] - w;
        }
    }
    cout << "事件的最早发生时间和最迟发生时间：" << endl;
    for (int i = 0; i < n; i++)
        cout << ve[i] << "\t" << vl[i] << endl;
    cout << "关键活动路径为:" << endl;
    for (int u = 0; u < n; u++) { //每次循环针对vi为活动开始点的所有活动
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            int e = ve[u];  //计算活动<vi, vj>的最早开始时间e
            int l = vl[v] - w; //计算活动<vi, vj>的最迟开始时间l
            if (e == l) //若为关键活动，则输出<vi, vj>
                cout << "<" << u << "," << v << ">" << endl;
        }
    }
    return 1;
}

int main() {
    int u, v, w;
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    memset(in, 0, sizeof(in));
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        in[v]++;
    }
    CriticalPath();
    return 0;
}
/*测试数据
6 8
0 1 2
0 2 15
1 3 10
1 4 19
2 1 4
2 4 11
3 5 6
4 5 5
*/