对关键路径定义的疑惑

Question

网上说：关键路径是aoe网中从源点到终点的最长路径
王道书上：

这个关键路径是1->3->2->5>6 总权值为27对吧。如果我把f权值改为20，此时按定义的说法1->3->5->6不是权值最大即关键路径了吗？但是我们其实可以绕过走f这条路径仍然可以遍历其他节点，这样子f这条路径显得就不关键了啊？

我参考了大话数据结构，感觉我的想法没有问题。换句话说，绕过f的其他路径仍然满足制约关系，而且整体工程时间还变少了。
大话数据结构：

Answer 1

你好像觉得任一路径达到就完事了？
AOE是某点全部前置边都完成，才算达到该点啊。要达到5需要e、f都完成。

Answer 2

老实说，这些东西早都忘了，只是凭自己仅存的一点印象来说 …… 所以，如果说得不对请直接指出来。

关键路径是找的最大路径长度，目的是找到需要完成某项任务所需要的最小时间。举个例来说：

说明：

1. 原图顶点不带字母，说起来感觉不爽，所以都前缀一个字母 V
2. 为了描述得形象一点，路径长度用单位“天”来描述

• 比如说，要达到 V2，就必须经过 a 和 b 两个活动，而 b 活动的前提是 c 活动；a 活动和 b、c 活动没有直接关系，可认为并行

  所以，要达到 V2，就至少需要 max(a, b + c) 天，也就是 max(3, 4 + 8) = 12 天，我们把它记为 V2X（不要在意为什么是 X，只是给个名字而已，虽然可能不标准，但能描述清楚）。

• 同理，可以看出来 V3X = 8（不用解释了吧）
• 而 V5 则需要从两个路径中去判断，是 V5X = max(V2X + 6， V3X + 10) = 18，结果很神奇，两条路径都是 18 天，无差别，都可以选择。

接下来的情况就不细说了，直接给个图出来

节点右上的蓝色色就是到达此节点所需要的必要时间（即最大路径长度）。而蓝色的线条就是关键路径。只有一点，到 V5 那里两条路径（红色路径和紫色路径）无差别。所以一共有两条关键路径。两条关键路径可能增加了分析的复杂性，但结果是，完成工程需要 27 天。

关键路径的作用在于，路径上任意一个活动延期都会造成整体工期延后。而非关键路径则有一定的“伸缩性”。比如 a 活动最长可延期 11 天都不会影响到整体工期，但关键路径上的任意一个活动 (b, c, e, f, h) 只要延期，哪怕 1 天，就一定会造成工期延迟。

一般只要存在活动时间变化（路径长度变化）都应该重新计算关键路径。

• 如果 b 活动延期，关键路径就会变成 c ⇒ b ⇒ e ⇒ h
• 如果 a 延迟 15 天，关键路径就会变成 a ⇒ e ⇒ h
• ……

所以，结论：关键路径是完成工程的最小完成时间。至于题主说的，绕过 f 会减少工程整体时间，应该是有算错。注意我们针对某个顶来来说，找的是进入此顶点的最大路径，因为路径表示活动依赖，必须要顺序完成。