关键路径¶

以下面的 AOE 网为例。

flowchart LR
    A((V<sub>0</sub>)) -- a<sub>0</sub>=6 --> B((V<sub>1</sub>))
    A -- a<sub>1</sub>=4 --> C((V<sub>2</sub>))
    A -- a<sub>2</sub>=5 --> D((V<sub>3</sub>))
    B -- a<sub>3</sub>=1 --> E((V<sub>4</sub>))
    C -- a<sub>4</sub>=1 --> E
    D -- a<sub>5</sub>=2 --> F((V<sub>5</sub>))
    E -- a<sub>6</sub>=9 --> G((V<sub>6</sub>))
    E -- a<sub>7</sub>=7 --> H((V<sub>7</sub>))
    F -- a<sub>8</sub>=4 --> H
    G -- a<sub>9</sub>=2 --> I((V<sub>8</sub>))
    H -- a<sub>10</sub>=4 --> I

边表示活动，顶点表示事件。规定：

进入某顶点的活动都结束时，该顶点对应的事件发生。
顶点对应的事件发生后，从它出去的活动才开始。

关键路径：从起点（源点）\(V_0\) 到终点（汇点）\(V_8\) 的最长路径的长度。可能有多条。

求法¶

递推关系 1¶

事件 \(V_j\) 的最早发生时间记为 \(ve(j)\)。\(ve(0)=0\)，且有递推关系

\[ ve(j) = \max_{\left \langle k,j \right \rangle \in E(G)} \{ ve(k) + dut(\left \langle k,j \right \rangle) \} \]

这是按拓扑顺序的递推关系。实际在写代码时，一边拓扑排序一边计算递推值。

例子¶

因为要等所有进入该顶点的活动都结束，所以取最大值。

\[ ve(7) = \max \{ ve(4)+7, ve(5)+4 \} \]

\[ ve(8) = \max \{ ve(6)+2, ve(7)+4 \} \]

递推关系 2¶

在不推迟的情况下，事件 \(V_j\) 的最迟发生时间记为 \(vl(j)\)。\(vl(n-1)=ve(n-1)\)，且有递推关系

\[ vl(j) = \min_{\left \langle j,k \right \rangle \in E(G)} \{ vl(k) - dut(\left \langle j,k \right \rangle) \} \]

这是按拓扑逆序的递推关系。实际在写代码时，根据拓扑排序结果倒过来递推。

例子¶

因为是在不推迟的情况下，所以

\(V_8\) 最迟发生时间等于最早发生时间，即 \(vl(n-1)=ve(n-1)\)。
算时间时取最小值，尽可能早地让事件发生。

\[ vl(4) = \min \{ vl(6)-9, vl(7)-7 \} \]

\[ vl(0) = \min \{ vl(1)-6, vl(2)-4, vl(3)-5 \} \]

判断关键路径中的活动¶

如果活动 \(a_i\) 由 \(\left \langle j,k \right \rangle\) 表示，则

\(a_i\) 的最早发生时间记为 \(e(i)\)。

\[ e(i)=ve(j) \]
在不推迟的情况下，\(a_i\) 的最迟发生时间记为 \(l(i)\)。

\[ l(i)=vl(k)-dut(\left \langle j,k \right \rangle) \]
满足 \(e(i)=l(i)\) 的 \(a_i\)，即为关键路径中的活动。

考虑到关键路径可能有多条，在算总长度时，不能简单地把所有满足条件的 \(dut(\left \langle j,k \right \rangle)\) 全加起来。

代码实现¶

代码中，\(0\) 是源点，\(N-1\) 是汇点。

int N;                           // 顶点数量
vector<pair<int, int>> G[MAX_N]; // 邻接表，first=顶点, second=权值
int in[MAX_N];                   // 存储每个顶点的入度
int ve[MAX_N], vl[MAX_N];        // ve 和 vl

bool critical_path(vector<int>& ans)
{
    // 把 ve 都初始化为 0
    for (int i = 0; i < N; i++)
    {
        ve[i] = 0;
    }

    // 记录拓扑排序的结果
    stack<int> s;

    // 拓扑排序
    queue<int> q;
    for (int i = 0; i < N; i++)
    {
        if (!in[i]) q.push(i);
    }
    while (q.size())
    {
        int v = q.front(); q.pop();
        s.push(v);

        for (pair<int, int>& adj : G[v])
        {
            if (--in[adj.first] == 0) q.push(adj.first);

            // 递推 ve
            ve[adj.first] = max(ve[adj.first], ve[v] + adj.second);
        }
    }

    // 有环
    if (s.size() != N)
    {
        return false;
    }

    // 把 vl 都初始化为最大值 ve(n-1)
    for (int i = 0; i < N; i++)
    {
        vl[i] = ve[t.top()];
    }

    while (s.size())
    {
        int v = s.top(); s.pop();

        for (pair<int, int>& adj : G[v])
        {
            // 按拓扑逆序递推 vl
            vl[v] = min(vl[v], vl[adj.first] - adj.second);
        }
    }

    // 找出一条关键路径
    int v = 0;
    ans.push_back(0);
    while (v != N - 1)
    {
        for (pair<int, int>& adj : G[v])
        {
            int ee = ve[v];
            int el = vl[adj.first] - adj.second;
            if (ee == el)
            {
                v = adj.first;
                ans.push_back(v);
                break;
            }
        }
    }
    return true;
}