★ FEATURED ARTICLE 1. 先搞清楚“关键路径”到底在算什么做项目管理、工程排期或者哪怕只是在给一个软件迭代排计划的人基本都躲不开一个问题这事儿最快什么时候能完很多人的第一反应是把所有任务的耗时加起来但干过活的人都知道项目里大量任务是并行的——你写后端的时候前端也没闲着你打地基的时候采购已经在订钢筋了。所以真正的完工时间不是所有任务之和而是最长的那个依赖链。关键路径法Critical Path MethodCPM就是干这个的。它把工程抽象成一张有向无环图DAG节点是“事件”比如“地基完成”“接口联调完成”边是“活动”就是具体要做的事边上标的数字就是这件事的耗时。在这张图上从起点到终点可能有很多条路径其中总耗时最长的路径就是关键路径这个最长耗时就是工程的最短完工时间。为什么要花力气找它因为只有关键路径上的活动才是真正决定工期的活动。关键路径上任何一个活动延误一天整个项目就延误一天反过来想压缩工期也只能先压缩关键路径上的活动动别的路径是白费劲。这就是“关键”两个字的含义——它是整个项目的命门。这套方法上世纪五十年代就在大型工程里用了到现在依然是项目管理的基本功。不管你是负责一栋楼的施工还是带一个二十人的研发团队只要你手上有依赖关系清晰、耗时相对可估算的任务清单关键路径分析都能帮你回答两个问题最早什么时候能干完想提前该压哪条线这篇文章我不会只停留在概念上。我会用一个具体的工程网络图把从建图、算事件时间、算活动时间到最终圈定关键路径的完整过程手工走一遍再给出可以直接抄走的代码实现最后聊聊我在真实项目里踩过的坑。看完你就能自己动手算了不管是用Excel、手算还是写代码。2. 手工推导一张精心设计的图看懂全部计算逻辑2.1 一个足够典型的工程网络讲理论干巴巴的我们直接拿一个模拟项目说事。假设某个工程要完成我们把它拆成8个活动、6个里程碑事件编号如下事件1开工事件2基础方案完成事件3主体结构到位事件4设备安装完毕事件5内部装修完工事件6竣工验收活动关系这样安排活动前置事件后续事件耗时天a1123a2132a3242a4253a5344a6352a7463a8561先把图画出来上班不用画多漂亮能看清就行开工后a1、a2两条线同时推进a1做完才能做a3、a4a2做完才能做a5、a6最后a7、a8汇聚到竣工验收。这是个典型的并行结构很适合用来讲透计算逻辑。2.2 四个关键数组一个都不能少手算关键路径本质上是填四个数组。我先把它们交代清楚后面就不迷糊了ve(i)事件 i 的最早发生时间。也就是说所有到达事件 i 的活动都完成时最早是哪一刻。vl(i)事件 i 的最迟发生时间。也就是说在不拖垮整个工期的前提下事件 i 最晚可以到什么时候发生。e(i)活动 i 的最早开始时间。活动 a 的前置事件一旦触发它就能立刻开工所以它等于前置事件的 ve。l(i)活动 i 的最迟开始时间。等于后继事件的 vl 减去活动本身耗时。一个活动如果 e l说明它一天都不能晚晚一天整个项目就晚一天——这种活动就是关键活动串起来就是关键路径。2.3 从左往右推最早时间ve计算 ve 的口诀是顺着拓扑序取最大值。因为一个事件可能有好几个前置活动必须等所有前置都完成这个事件才算发生所以取各条路径中的最大值。事件1开工ve(1)0。只有 a1 指向事件2所以 ve(2) ve(1) 3 3。只有 a2 指向事件3ve(3) 0 2 2。事件4有两条来路a3 从事件2来耗时2a5 从事件3来耗时4。所以 ve(4) max(ve(2)2, ve(3)4) max(5, 6) 6。事件5也是两条来路a4 从事件2来耗时3ve(2)36a6 从事件3来耗时2ve(3)24。所以 ve(5)max(6,4)6。事件6有两条a7 从事件4来ve(4)39a8 从事件5来ve(5)17。所以 ve(6)max(9,7)9。里程碑出来了整个工程最短要9天。注意这里体现了一个特别容易错的观点最短工期不是“最长的单个活动”而是“最长的路径总和”。9天来自 1→3→4→6 这条线243而不是任何单个活动。2.4 从右往左推最迟时间vl算完最早要反着来一遍。vl 的口诀是逆着拓扑序取最小值。原因很直观事件 i 有好几个后继活动每个后继活动都有它自己的最迟开始时间事件 i 必须早到能满足所有后继活动最迟开始的要求所以取最小值。终点事件的 vl 等于 vevl(6)9。事件5只有一个后继活动 a8vl(5) vl(6) - 1 8。事件4只有后继 a7vl(4) 9 - 3 6。事件3有两个后继a5 指向事件4耗时4a6 指向事件5耗时2。vl(3) min(vl(4)-4, vl(5)-2) min(6-4, 8-2) min(2, 6) 2。事件2也有两个后继a3 指向事件4耗时2a4 指向事件5耗时3。vl(2) min(vl(4)-2, vl(5)-3) min(6-2, 8-3) min(4, 5) 4。事件1只有一个后继 a1、a2。vl(1) min(vl(2)-3, vl(3)-2) min(4-3, 2-2) min(1, 0) 0。算完 vl(1)0说明整个推算自洽因为起点不可能晚于0开始。2.5 活动时间与关键路径判定有了 ve 和 vle 和 l 就是查表计算。e 是活动起点事件的 vel 是终点事件的 vl 减去耗时我直接整理成表活动耗时最早开始 e最迟开始 l时差 l-e是否关键a13ve(1)0vl(2)-311否a220vl(3)-200是a32ve(2)3vl(4)-241否a433vl(5)-352否a54ve(3)2vl(4)-420是a622vl(5)-264否a73ve(4)6vl(6)-360是a81ve(5)6vl(6)-182否时差为0的活动是 a2、a5、a7串起来是1 → 3 → 4 → 6总耗时 2439 天这就是关键路径。注意一个现象a1 的时差只有1a3 的时差也是1。它们不是关键活动但很“接近关键”——这种活动在项目管理里叫近关键活动。真实项目中近关键活动往往比关键活动更危险因为大家的目光都盯着关键路径一压缩关键路径近关键活动就可能变成新的关键路径这个我在后面实操篇专门讲。3. 代码落地用拓扑排序把关键路径算得明明白白3.1 为什么必须靠拓扑排序手工算小图没问题但现实里的项目动辄几百个任务手算根本不现实。而且要保证 ve 的计算顺序正确必须按拓扑序遍历——也就是保证算到某个事件时它的所有前置事件都已经算完了。如果图里有环说明依赖关系出现了循环定义这本身就是一个需要排查的工程错误。拓扑排序有两种常见实现Kahn 算法不断删除入度为0的节点和 DFS 深度优先。我习惯用 Kahn 算法因为它在算 ve 的同时天然支持“入度归零逐个解锁”的逻辑代码也更直观。3.2 Python 实现从建图到输出关键路径我直接用 Python 把上面那个例子跑一遍。核心数据结构是两个字典一个存每个事件的后继活动列表一个存每个事件的前驱活动列表。边用 (后继节点, 耗时) 表示。from collections import defaultdict, deque def critical_path(n, edges): n: 事件节点数1号到n号 edges: 边列表每个元素为 (起点, 终点, 耗时) 返回: 最短工期、关键活动列表 # 邻接表正向和反向都建 graph defaultdict(list) # 正向起点 - [(终点, 耗时)] reverse_graph defaultdict(list) # 反向终点 - [(起点, 耗时)] indegree [0] * (n 1) for u, v, w in edges: graph[u].append((v, w)) reverse_graph[v].append((u, w)) indegree[v] 1 # 拓扑排序 计算最早发生时间 ve ve [0] * (n 1) q deque([i for i in range(1, n 1) if indegree[i] 0]) topo_order [] while q: u q.popleft() topo_order.append(u) for v, w in graph[u]: ve[v] max(ve[v], ve[u] w) indegree[v] - 1 if indegree[v] 0: q.append(v) if len(topo_order) ! n: raise ValueError(图中存在环无法计算关键路径) # 逆拓扑序计算最迟发生时间 vl vl [float(inf)] * (n 1) vl[n] ve[n] # 终点事件的最迟 最早 for u in reversed(topo_order): for v, w in graph[u]: vl[u] min(vl[u], vl[v] - w) # 遍历所有活动判断关键活动 critical_activities [] for idx, (u, v, w) in enumerate(edges): e ve[u] l vl[v] - w if e l: critical_activities.append((fa{idx1}, u, v, w)) return ve[n], critical_activities # 示例8个活动、6个事件 edges [ (1, 2, 3), # a1 (1, 3, 2), # a2 (2, 4, 2), # a3 (2, 5, 3), # a4 (3, 4, 4), # a5 (3, 5, 2), # a6 (4, 6, 3), # a7 (5, 6, 1), # a8 ] duration, criticals critical_path(6, edges) print(最短工期:, duration, 天) print(关键活动:) for name, u, v, w in criticals: print(f {name}: 事件{u} - 事件{v}, 耗时{w}天)运行结果最短工期: 9 天 关键活动: a2: 事件1 - 事件3, 耗时2天 a5: 事件3 - 事件4, 耗时4天 a7: 事件4 - 事件6, 耗时3天和手算结果完全一致。如果你想把整个关键路径上的事件序列也打印出来可以从起点开始沿着关键活动做一次 DFS或者在建表时多做一步记录都不复杂。3.3 多起点、多终点的处理技巧真实项目往往不是单一起点、单一终点。比如一个平台有多个独立模块可以并行启动有的模块甚至到不了最终的验收节点。这种情况下直接套上面的代码会出问题——终点事件不唯一vl 的初始化就没法做。我的做法是加虚拟节点加一个超级起点 S从 S 向所有入度为0的事件连一条耗时0的边加一个超级终点 T从所有出度为0的事件向 T 连一条耗时0的边。然后在新图上跑标准算法。这样做的好处是不改变任何真实活动的耗时和依赖关系纯粹是让图变得“规整”。工程上有个等价的做法不建虚拟节点直接初始化所有起点 ve0对所有终点取 vlmin(ve(终点))。但我个人推荐虚拟节点方案因为它把问题变成了标准问题代码不用写特殊分支后续如果要输出路径也更顺。4. 实际工程里的关键路径教科书不讲的坑和技巧4.1 依赖关系可能比你想的多我给某个内部系统排期时最初大家列的依赖清单清一色是技术依赖——A模块的接口要先于B模块的开发。干到一半发现真正卡脖子的依赖反而是“人”的依赖能写那个算法的工程师只有一个他同时被三个任务占用。这种资源约束不体现在常规的 AOE 网里但会让关键路径完全变样。处理方式有两种。简单粗暴的方式把一个任务拆成互斥的串行段比如“张三先做X3天再做Y2天”把资源冲突直接变成依赖关系。正规一点的方式先算一次 CPM 得到理想关键路径再用资源均衡Resource Leveling的手段调整排期然后重新算。千万不要忽略资源约束直接排期那种排期表只能存在于 PPT 里。4.2 对关键路径压缩要准备好“关键路径会转移”这是我踩过最深的坑。某次项目延期我判断关键路径是 A→B→C于是拼命压缩 C 活动的时间找了两个人并行干活硬生生把 C 从4天压到2天。结果总工期只提前了半天因为压缩之后原本只剩1天余量的 D→E 这条线变成了新的关键路径原来的关键活动 C 反而有了余量。这说明一个重要的道理关键路径不是一条静态的线而是一个动态的结果。每压缩一次都必须重新计算关键路径。压缩的时候优先挑“压缩成本低”的关键活动压缩到一定程度后要停下来重算不能闭着眼睛一直压同一条线。判断压缩哪个活动业界常用“时间-成本权衡”Time-Cost Trade-off把每个关键活动估算一个“赶工成本/天”优先压缩单位成本最低的关键活动。压缩后立刻重算直到出现新的关键路径或者压缩成本超出延期损失。4.3 CPM 和 PERT 别混着用CPM 假定活动耗时是确定的——3天就是3天。但真实世界的活动耗时往往是一个范围尤其研发类任务“顺利的话2天不顺利可能5天”。这时候就要用 PERT计划评审技术它对每个活动采用三点估算乐观时间 t_o一切顺利时的耗时悲观时间 t_p各种不顺全碰上的耗时最可能时间 t_m正常情况下的耗时然后计算期望耗时 t_e (t_o 4*t_m t_p) / 6。PERT 和 CPM 的图模型完全一样计算逻辑也完全一样只是边的权重从固定值换成了期望值。我见过有人把最可能时间直接当固定值去跑 CPM结果工期天天“意外”延误。如果你的任务耗时不确定性比较大建议先用三点估算求出期望耗时再跑关键路径。4.4 免费时差和总时差要分清楚活动 a1 在例子里的时差是1天意思是它最多可以晚开始1天而不影响总工期。但这里说的是总时差Total Float它是全局概念。还有一种自由时差Free Float指的是不影响所有后继活动最早开始时间的前提下本活动可以延误的天数。a1 的自由时差是0——它晚1天虽然不影响总工期9天但会连累后继活动 a3、a4 晚1天开始可能导致它们从近关键变成关键。实际排期时我一般看自由时差而不是总时差。自由时差为负的活动说明依赖关系写错了自由时差很小0或1的活动要重点盯防。5. 常见问题速查与经验清单我在做关键路径分析时经常遇到下面这些问题整理成一个速查表写代码和排期的时候对着看能省不少事。现象可能原因处理方式图中有环拓扑排序做不下去依赖关系定义出现了循环把环打印出来逐一核对通常是两个任务互相“等对方”的错误描述ve(终点) 与手工估的工期对不上漏了某个并行路径或某个活动耗时写错从终点反向回溯最长路径逐个核对每条入边所有活动时差都是0图是纯串行结构或建模粒度太粗检查是否漏了并行活动任务拆分不够细也会导致全链关键压缩关键路径后总工期没变化近关键路径变成新的关键路径压缩后立即重算观察新关键路径的变化多个终点事件 vl 不唯一图不是单源单汇加虚拟起点/终点统一 vl 初始化活动耗时估计很难准确任务不确定性大改用 PERT 三点估算把分布信息转化为期望耗时资源冲突导致实际排期与 CPM 结果严重偏离CPM 没有建模资源约束先做资源均衡冲突任务转为串行依赖再重算再分享两个实用性很强的技巧。第一个关键路径分析别只做一次。项目启动时做一次拿到基线之后每两周或每次范围变更后重新算一次。很多项目延期不是一开始没算对而是中途加了需求、换了人、调了优先级关键路径早就变了但项目计划还停留在开工时的版本。我习惯把关键路径分析脚本固化下来每次更新任务清单就重新跑一遍几分钟出结果开会时直接贴图说话。第二个把“近关键活动”的时差画出来。我做过一个项目关键路径总工期稳定但每周都有模块在延期原因就是大量近关键活动时差1-2天轮流“爆雷”每次爆一个总工期虽然没变但团队士气和管理成本很高。后来我在周报里加了一列“时差预警”把时差小于3天的活动全部标红提前给它们预备资源才算把这个问题压住。关键路径方法的价值不在于那张图本身而在于它能逼着你想清楚每一件事的依赖关系然后告诉你资源该往哪里投。它不会替你解决所有管理问题但能帮你在迷雾里找到那条真正决定成败的线。我在实际使用中最大的体会是算关键路径本身不难难的是愿意在项目前期把依赖关系和耗时老老实实梳理清楚。很多团队跳过这一步直接凭感觉排期最后只能天天救火。磨刀不误砍柴工这句话放在排期上再合适不过。
阅读完成 · 觉得有帮助？
