6.4.5 关键路径
原书定位
印刷页P240起,对应PDF第252页。下文为目视整理的知识提要;完整内容见原书对照。
AOE 网以顶点表示事件、带权有向边表示活动和持续时间,是 DAG。一个事件须等全部入边活动完成才能发生,因此工程最短完成时间等于源点到汇点的最长路径长度。
按拓扑序求事件最早时间,按逆拓扑序求最迟时间:
源点 ;汇点 。对活动 :
余量为 0 的活动是关键活动,串成的源汇路径是关键路径。关键活动延误会延误工程;缩短某一关键活动未必缩短工期,还要考虑其他关键路径和缩短后出现的新关键路径。
多个起点或终点可添加零持续时间的虚拟源、汇统一处理。关键路径求最长工期约束,与最短路径问题的递推目标不同。

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

图算法时间复杂度比较,原书P242。
对应练习
关联知识
原书对照
展开原书对照截图


