带过项目的同学都有过这种瞬间：老板问"能不能提前一周上线"，你脑子里刷地过一遍所有任务，然后发现——有的活拖两天没事，有的活拖一天，整个项目就得往后挪一天。
管住后者的，就是关键路径（Critical Path）。
这名字听起来像 PMP 的黑话，但它背后是一套能在 408 考卷上直接拿分的图论算法。今天把它从"项目管理"这层外衣里扒出来，看看到底在算什么。
一、先解决一个更基础的问题：任务能不能排成一条线
一个项目里，任务是有先后依赖的：写需求说明书，才能写代码；写完代码，才能测试。如果 A 必须在 B 之前，画一条从 A 指向 B 的边，整张图就是一张有向无环图（DAG）。
有环就有问题——A 等 B、B 等 C、C 又等 A，谁也别想开工。所以第一步，得判断"这些任务能不能排出一个合理的先后顺序"，这就是拓扑排序。
它的思路朴素到有点好笑：每次挑一个"没人依赖它"的活儿先干。用图论的话说，就是反复找入度为 0的顶点，删掉它和它发出的边。一直删下去：
- 删光了 → 得到一条合法顺序；
- 删不干净（还有顶点剩着）→ 图里有环，依赖关系自相矛盾。
Kahn 算法写出来就几行：
fromcollectionsimportdequedeftopological_sort(n,edges):# edges: [(u, v)]，表示 u 必须先于 vindeg=[0]*n g=[[]for_inrange(n)]foru,vinedges:g[u].append(v)indeg[v]+=1q=deque([iforiinrange(n)ifindeg[i]==0])order=[]whileq:u=q.popleft()order.append(u)forving[u]:indeg[v]-=1ifindeg[v]==0:q.append(v)returnorderiflen(order)==nelseNone# None 说明有环拓扑排序是 408 数据结构"图"一章的常客，常以选择题出现（比如"下面哪个序列是合法的拓扑序"），偶尔在大题里露脸。邻接表实现的时间复杂度是O ( V + E ) O(V+E)O(V+E)，这个结论要能张口就来。
二、光排出来还不够，得知道哪些活儿"拖不得"
拓扑排序只回答"能不能排、怎么排"。但老板问的是"提前上线行不行"，这要算的是时间。
这时候把图升级成AOE 网：顶点表示"事件"（某个里程碑完成了），边表示"活动"（一件事），边上带权值，表示这件事要花多少天。一个事件，必须等它所有入边代表的活动都干完，才算发生。
对每个事件，我们关心两个数：
- 最早发生时间 ve：这件事最早什么时候能成。它等于"所有通往它的事件里，最晚的一个最早时间 + 边权"。从源点一路往前推：
v e ( v j ) = max ( v i , v j ) ∈ E { v e ( v i ) + w ( v i , v j ) } ve(v_j) = \max_{(v_i, v_j) \in E}\{ve(v_i) + w(v_i, v_j)\}ve(vj)=(vi,vj)∈Emax{ve(vi)+w(vi,vj)}
- 最迟发生时间 vl：这件事最晚得在什么时候成，才不会拖累整体工期。从汇点往回倒推：
v l ( v i ) = min ( v i , v j ) ∈ E { v l ( v j ) − w ( v i , v j ) } vl(v_i) = \min_{(v_i, v_j) \in E}\{vl(v_j) - w(v_i, v_j)\}vl(vi)=(vi,vj)∈Emin{vl(vj)−w(vi,vj)}
有了事件的两个时间，边（活动）的松紧就出来了：
- 活动最早开始：e = v e ( v i ) e = ve(v_i)e=ve(vi)
- 活动最迟开始：l = v l ( v j ) − w l = vl(v_j) - wl=vl(vj)−w
- 时间余量：l − e l - el−e
时间余量为 0 的活动，就是关键活动。它们首尾相接，连成的那条从源点到汇点的最长路径，就是关键路径。
为什么是"最长"而不是"最短"？因为项目总工期等于从开始到结束最长的那条路——最短的路再快也没用，最后得等最慢的那条。所以关键路径 = DAG 里的最长路径，这跟 Dijkstra 求最短路径刚好是镜像。
三、用泡茶把整个流程过一遍
烧水 5 分钟、洗茶壶 1 分钟、洗茶杯 2 分钟、泡茶 1 分钟。依赖关系：烧水不依赖别的，洗壶洗杯不依赖烧水，但泡茶必须等烧水和洗壶都完成。
算下来你会发现，决定你多久能喝上茶的，是"烧水 → 泡茶"这条 6 分钟的路。洗茶杯那 2 分钟哪怕你多花一倍，只要别超过 6 分钟的总工期，就没人能察觉。余量，就是你可以摸鱼的空间；关键路径，就是你摸不得的地方。
这个道理放到软件工程里一模一样：真正决定发布日期的，永远不是那些"看起来忙"的活，而是那几件一环扣一环、半点拖不得的事。
四、顺带说一句
很多人学图论，是把拓扑排序、最短路径、最小生成树当成几个孤立算法去背的。其实它们回答的是同一个问题的不同侧面：在一堆有约束的事情里，怎么安排、怎么取舍。谁先谁后（拓扑）、怎么最快（最短路径）、怎么最省（最小生成树）、哪里拖不得（关键路径）。
把这四件事摆在一起看，图这一章反而简单了——你不是在背四个算法，你是在学"怎么给有依赖的事做计划"。
数据结构是 408 的重头戏，想系统跟学的，推荐 B站【408实验室】的《数据结构》。
图相关的兄弟篇我也都写过：为什么导航能算出"最短路线"（Dijkstra 算法）、为什么修路要"连成网、又花最少的钱"（最小生成树）、一个数组就敢说判断亲戚关系快得离谱（并查集），配合着看，图这一章能串成一条线。
备考时被"关键路径求 ve/vl 老是算错"卡住的，可以把这类题丢进 CoLearn（yantucs.com）的AI 答疑让 AI 一步步带你把 ve、vl 各推导一遍，再用AI 错题集把反复错的那几道收起来专项突破。
