> For the complete documentation index, see [llms.txt](https://docs.1l.lol/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.1l.lol/graph-theory/critical-path.md).

# 关键路径

### AOE 网

**AOE 网**（Activity On Edge）是带权有向无环图：顶点表示事件，边表示活动，边权表示活动持续时间。

### 两个关键时间

* **事件最早发生时间 ve\[u]**：从源点到 u 的最长路径
* **事件最迟发生时间 vl\[u]**：不影响总工期的前提下，u 最晚发生时间

### 计算

```cpp
// ve：按拓扑序正推
ve[v] = max(ve[v], ve[u] + w);

// vl：按逆拓扑序倒推
vl[u] = min(vl[u], vl[v] - w);
```

### 关键活动与关键路径

* **关键活动**：满足 `ve[u] + w == vl[v]` 的边
* 把所有关键活动连起来即**关键路径**，决定总工期

### 应用

项目管理、工程工期优化；缩短关键活动才能缩短总工期。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://docs.1l.lol/graph-theory/critical-path.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.