关键路径¶
以下面的 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\) 是汇点。