6.4.5 关键路径

教材导航 · 第6章

原书定位

印刷页P240起,对应PDF第252页。下文为目视整理的知识提要;完整内容见原书对照。

AOE 网以顶点表示事件、带权有向边表示活动和持续时间,是 DAG。一个事件须等全部入边活动完成才能发生,因此工程最短完成时间等于源点到汇点的最长路径长度。

按拓扑序求事件最早时间,按逆拓扑序求最迟时间:

ve[v]=max⁡u→v{ve[u]+w(u,v)}ve[v]=\max_{u\to v}\{ve[u]+w(u,v)\} vl[u]=min⁡u→v{vl[v]−w(u,v)}vl[u]=\min_{u\to v}\{vl[v]-w(u,v)\}

源点 ve=0ve=0;汇点 vl=vevl=ve。对活动 u→vu\to v:

e=ve[u],l=vl[v]−w(u,v),余量=l−ee=ve[u],\quad l=vl[v]-w(u,v),\quad \text{余量}=l-e

余量为 0 的活动是关键活动,串成的源汇路径是关键路径。关键活动延误会延误工程;缩短某一关键活动未必缩短工期,还要考虑其他关键路径和缩短后出现的新关键路径。

多个起点或终点可添加零持续时间的虚拟源、汇统一处理。关键路径求最长工期约束,与最短路径问题的递推目标不同。

事件、活动时间与关键路径计算

事件、活动时间与关键路径计算,原书P242。

图算法时间复杂度比较

图算法时间复杂度比较,原书P242。

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P240,PDF第252页

原书对照,原书P241,PDF第253页

原书对照,原书P242,PDF第254页