(53)王道数据结构-关键路径
原文地址:关键路径
基本概念
如果此时我们为每个任务添加一个权重，表示任务所需要花费的时间，那么我们的后续任务就需要前置任务全部按时间完成之后才能继续。只要计算出这些最拖延工期的任务，得到一条关键路径，我们就可以得到完成整个工程最早的时间以及各项任务可以在什么时候开工了。
操作步骤
只需要计算两个东西，一个是事件最早完成时间（也就是要完成这个事件最快要多久），还有一个是事件最晚开始时间（就是这个事件在不影响工期的情况下最晚可以多久开始）
A代表某个任务（事件），B代表另一个任务，我们需要先花费2天时间完成A之后，才能开始B，活动包括时间用边来表示，我们将边作为活动的图称为AOE图
AOE图
首先一开始是A，因为只有一个起点A肯定是可以直接开始的，所以说最早和最晚时间都是0（注意如果出现多个起点的话，最晚开始时间就不一定了）
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | |||||
| Vi | 0 |
第一步
A之后是B和C，由于不需要提前完成其他任务所以B和C的最早完成时间分别为3,2
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | |||
| Vi | 0 |
第二步
其中E需要先完成A和B，所以E的最早完成时间是A+B=3+3=6。D需要完成B和C,因为有两条路径，我们选择最长的路径A->C->D
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | |
| Vi | 0 |
第三步
因为到大F有三条路径，按照之前的规则，依然选择最长的路径A->C->D->F
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | 8 |
| Vi | 0 |
第四步
工作最晚时间需要从终点向起点看，其中终点是8，因为最快是8天内结束的
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | 8 |
| Vi | 0 | 8 |
第五步
E最早需要6天才能到达，但F到E只需要1天，所以最晚需要8-1=7天
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | 8 |
| Vi | 0 | 7 | 8 |
第六步
D到F需要两天，所以D需要第6天开始
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | 8 |
| Vi | 0 | 6 | 7 | 8 |
第七步
C中有两个活动，一个指向D，一个指向F，需要单独计算每一个活动
1.C->F中用F最晚开始时间减去任务时间=8-3=5, 此时C最晚可以从第5天开始
2.C->D中用D最晚开始时间减去任务时间=6-4=2，此时C的最早开始时间是2，所以说C不能晚开始。综上，C不能晚点开始，只能从第2天就开始，因为要满足D的条件
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | 8 |
| Vi | 0 | 2 | 6 | 7 | 8 |
最后一步
B中有两个活动，一个指向E一个指向D:
1.B->E:用E最晚开始时间减去任务时间=7-3=4，因此B最晚可以第4天开工
2.B->D:用D最晚开始时间减去任务时间=6-2=4，同上B最晚开始时间可以是第4天
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| Ve | 0 | 3 | 2 | 6 | 6 | 8 |
| Vi | 0 | 4 | 2 | 6 | 7 | 8 |