某软件项目的活动图如下图所示,其中顶点表示项目的里程碑,连接顶点的边表示包含的活动,变色数字表示活动持续时间(天)。完成该项目的最少时间为多少天?由于某种原因,现在需要同一个开发人员完成BC和BD,则完成该项目的最少时间为多少天?

D
D
E
E
I
I
F
F
A
A
J
J
H
H
C
C
G
G
B
B
2
2
3
3
2
2
4
4
5
5
2
2
4
4
5
5
3
3
6
6
2
2
START
START
FINISH
FINISH
3
3
6
6
Viewer does not support full SVG 1.1

由上面这个图可以知道,任务时从活动A开始的,到活动J结束。

第一问就很简单了,求完成所有项目的最少时间,那只要求一条完成时间最长的路径就可以了。

A
A
G,7
G,7
H,12
H,12
D,4
D,4
E,10
E,10
F,13
F,13
C,5
C,5
B,2
B,2
J,18
J,18
I,13
I,13
2
2
5
5
4
4
6
6
7
7
10
10
13
13
13
13
12
12
13
13
18
18
17
17
15
15
Viewer does not support full SVG 1.1

由这个分析图可以知道,完成所有的活动最少要用18天的时间。

第二问,加了一个条件,BC和BD都是由一个人来完成,由上面这个图也很好分析,这个时候这个人面临着两个选择,先做BC或者先做BD。

先来看先做BC的情况。先做BC也就意味着由C发展的这一支活动还是跟以前运行的一样,但是由D发展的这一支,就需要等3天的时间,最后算得最少完成时间为21天。

再看先做BD的情况。先做BD也就意味着由D发展的这一支活动还是跟以前运行一样,但是由C发展的这一支,就需要等上两天的时间,最后算得最少完成时间为20天。

但是答案却是先做BC的情况,也就是最少完成时间是21天,为什么会这样呢?明明可以先做BD然后可以提前一天完成所有的项目。

然后我就认为答案错了就从网上找原题,发现所有的答案都是21天,解析说的是走最长的路径,不理解,这明明是两种情况,有一条最优的情况不选,却要走最长的,难道我对最少完成时间理解有误?

有待解决。