AOE/AOV网下的关键路径

算法

在做那本王道考研数据结构书的时候发现这个东西，以前没听说过（太菜了

Published

October 2, 2023

Content note — Known errors · 明显错误

AOE/AOV 定义和关键路径结论有明显错误，代码也存在索引 bug。

AOV 通常是顶点表示活动、边表示优先关系；AOE 是边表示活动、顶点表示事件，文中写成了同一种。
“所有关键点一定组成一棵树”不成立，关键活动可形成子图。
代码里 iscritical [j] = true 应重新核对，j 是邻接表下标而不是点编号。

AOE/AOV网下的关键路径

在做那本王道考研数据结构书的时候发现这个东西，以前没听说过（太菜了

1.定义

一般而言这个模型可以用来表示一个项目的子项之间的依赖关系，用来管理项目进度。

1.1 AOV网

AOV网指的是Activity-On-Vertex，用点表示事件，用边表示事件之间的关系（活动），边权是活动时间。这是一个DAG（有向无环图）

1.2 AOE网

AOE网指的是Activity-On-Edge，用点表示事件，用边表示事件之间的关系（活动），边权是活动时间。这也是一个DAG（有向无环图）

1.3 关键路径

如果改变一条路径上的任意一条边的边权，都可以加速项目的最终进度，那么这条路径被称为关键路径。

2.计算方法

计算关键路径事实上只是在DAG上的简单dp，首先计算一个事件的最早开始时间，然后计算一个事件的不会影响到最终项目进度的最晚开始时间，当最早开始时间等于最晚开始时间，那么这个点是一个关键的点。所有的关键点一定会组成一颗树。树上的所有路径都是关键路径。

首先计算拓扑序，然后在拓扑序上正向递推一个事件的最早开始时间，最后在逆拓扑序上递推最迟开始时间

\[ for\ each\ edge\ <u \rightarrow v> \ \: \] \[ \begin{aligned} minStartTime[v] &= Max(minStartTime[v],minStartTime[u]+w[u][v])\\ maxStartTime[u] &= Min(maxStartTime[u],maxStartTime[v]-w[u][v]) \end{aligned} \]

第一个点的 minStartTime = 0，最后一个点的 maxStartTime = minStartTime

3.代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1e6+7, INF = 0x3f3f3f3f;
template <typename _TP>
inline _TP qread(_TP &X){
    char ch=0;int w;X=0;
    while(!isdigit(ch)){w=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^'0');ch=getchar();}
    X=w?-X:X;
    return X;
}
queue <int> q;
vector <int> v[MAXN],d[MAXN],pre[MAXN],predis[MAXN];
int ind[MAXN];
inline void adde(const int x,const int y,const int z){ 
    v[x].push_back(y);
    d[x].push_back(z);
    pre[y].push_back(x);
    predis[y].push_back(z);
    ind[y]++;
}
int topoOrder[MAXN],vis[MAXN],cntTopo=0;
void topoSort(int s){
    vis[s]=1;
    q.push(s);
    int nxt;
    while(!q.empty()){
        s = q.front();
        vis[s]=1; 
        q.pop();
        topoOrder[++cntTopo]=s;
        for(int i=0;i<v[s].size();i++){
            nxt = v[s][i];
            if(!vis[nxt]){ 
                if(!(--ind[nxt])){
                    q.push(nxt);
                }
            }
        }
    }
}
int minStart[MAXN],maxStart[MAXN],n,m;
bool iscritical [MAXN];
inline int Max(const int a,const int b){
    return a>b?a:b;
}
inline int Min(const int a,const int b){
    return a<b?a:b;
}
inline void PRINT(const int *tmp){
    for(int i=1;i<=n;i++){
        cout<<tmp[i]<<' ';
    }
    cout<<'\n';
}
int main(){
    int x,y,z;
    qread(n);qread(m);
    for(int i=1;i<=m;i++){
        qread(x);qread(y);qread(z);
        adde(x,y,z);
    }
    int s=1;        //start node
    topoSort(s);
    cout<<"topoOrder: ";
    PRINT(topoOrder); 
    int now,nxt;
    for(int i=1;i<=n;i++){
        now = topoOrder[i];
        for(int j=0;j<v[now].size();j++){
            nxt = v[now][j];
            minStart[nxt] = Max(minStart[nxt],minStart[now]+d[now][j]);
        }
    }
    cout<<"minStart: ";
    PRINT(minStart); 
    memset(maxStart,0x3f,sizeof(maxStart));
    maxStart[topoOrder[n]] = minStart[topoOrder[n]];
    for(int i=n;i>=1;i--){
        now = topoOrder[i];
        for(int j=0;j<pre[now].size();j++){
            nxt = pre[now][j];
            maxStart[nxt] = Min(maxStart[nxt],maxStart[now]-predis[now][j]);
        }
    }
    cout<<"maxStart: ";
    PRINT(maxStart); 
    for(int i=1;i<=n;i++){      //go through all edges
        for(int j=0;j<v[i].size();j++){
            nxt = v[i][j];
            int minHappen = minStart[i];
            int maxHappen = maxStart[nxt]-d[i][j];
            if(maxHappen - minHappen == 0){
                iscritical[i] = iscritical [j] = true;
            }
        }
    }
    cout<<"critical point: ";
    for(int i=1;i<=n;i++){
        if(iscritical[i])cout<<i<<' ';
    }
    return 0;
}

4.样例

第一行n,m是点的数量和边的数量

样例来自王道数据结构考研复习指导的习题13