带过项目的同学都有过这种瞬间老板问能不能提前一周上线你脑子里刷地过一遍所有任务然后发现——有的活拖两天没事有的活拖一天整个项目就得往后挪一天。管住后者的就是关键路径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]1qdeque([iforiinrange(n)ifindeg[i]0])order[]whileq:uq.popleft()order.append(u)forving[u]:indeg[v]-1ifindeg[v]0:q.append(v)returnorderiflen(order)nelseNone# None 说明有环拓扑排序是 408 数据结构图一章的常客常以选择题出现比如下面哪个序列是合法的拓扑序偶尔在大题里露脸。邻接表实现的时间复杂度是O ( V E ) O(VE)O(VE)这个结论要能张口就来。二、光排出来还不够得知道哪些活儿拖不得拓扑排序只回答能不能排、怎么排。但老板问的是提前上线行不行这要算的是时间。这时候把图升级成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)eve(vi)活动最迟开始l v l ( v j ) − w l vl(v_j) - wlvl(vj)−w时间余量l − e l - el−e时间余量为 0 的活动就是关键活动。它们首尾相接连成的那条从源点到汇点的最长路径就是关键路径。为什么是最长而不是最短因为项目总工期等于从开始到结束最长的那条路——最短的路再快也没用最后得等最慢的那条。所以关键路径 DAG 里的最长路径这跟 Dijkstra 求最短路径刚好是镜像。三、用泡茶把整个流程过一遍烧水 5 分钟、洗茶壶 1 分钟、洗茶杯 2 分钟、泡茶 1 分钟。依赖关系烧水不依赖别的洗壶洗杯不依赖烧水但泡茶必须等烧水和洗壶都完成。算下来你会发现决定你多久能喝上茶的是烧水 → 泡茶这条 6 分钟的路。洗茶杯那 2 分钟哪怕你多花一倍只要别超过 6 分钟的总工期就没人能察觉。余量就是你可以摸鱼的空间关键路径就是你摸不得的地方。这个道理放到软件工程里一模一样真正决定发布日期的永远不是那些看起来忙的活而是那几件一环扣一环、半点拖不得的事。四、顺带说一句很多人学图论是把拓扑排序、最短路径、最小生成树当成几个孤立算法去背的。其实它们回答的是同一个问题的不同侧面在一堆有约束的事情里怎么安排、怎么取舍。谁先谁后拓扑、怎么最快最短路径、怎么最省最小生成树、哪里拖不得关键路径。把这四件事摆在一起看图这一章反而简单了——你不是在背四个算法你是在学怎么给有依赖的事做计划。数据结构是 408 的重头戏想系统跟学的推荐 B站【408实验室】的《数据结构》。图相关的兄弟篇我也都写过为什么导航能算出最短路线Dijkstra 算法、为什么修路要连成网、又花最少的钱最小生成树、一个数组就敢说判断亲戚关系快得离谱并查集配合着看图这一章能串成一条线。备考时被关键路径求 ve/vl 老是算错卡住的可以把这类题丢进 CoLearnyantucs.com的AI 答疑让 AI 一步步带你把 ve、vl 各推导一遍再用AI 错题集把反复错的那几道收起来专项突破。
