为了能够确定工程的最早完成时间，只需在开始事件到完成事件间寻找最长有向路径，它的长度就是答案。路径长度是指这条路径上所有活动时间的总和。 可以通过求解树中每个结点（事件）的最早完成时间，来计算整个工程的最早完成时间。若
E
a
r
l
i
e
s
t
[
i
]
Earliest[i]
Earliest[i]表示结点
i
i
i 的最早完成时间，
C
v
,
w
C_{v,w}
Cv,w表示
<
v
,
w
>
<v,w>
<v,w>边的权重，则有：
E
a
r
l
i
e
s
t
[
1
]
=
0
E
a
r
l
i
e
s
t
[
w
]
=
max
<
v
,
w
>
∈
E
(
E
a
r
l
i
e
s
t
[
v
]
+
c
v
,
w
)
Earliest[1] = 0\\Earliest[w]=\max_{<v,w>\in E}(Earliest[v]+c_{v,w})
Earliest[1]=0Earliest[w]=<v,w>∈Emax(Earliest[v]+cv,w)
同样，还可以求解每一事件
i
i
i 在不影响整个工程完成情况下的允许最晚完成时间
L
a
t
e
s
t
[
i
]
Latest[i]
Latest[i] 。计算是从结束事件开始，设结束顶点为事件
n
n
n，按事件拓扑的相反次序逐个顶点推算，直到工程的初始顶点为止。结束顶点的最晚完成事件等于它的最早完成时间，其他顶点按下式计算：
L
a
t
e
s
t
[
n
]
=
L
a
t
e
s
t
[
n
]
L
a
t
e
s
t
[
v
]
=
min
<
v
,
w
>
∈
E
(
L
a
t
e
s
t
[
w
]
−
C
v
,
w
)
Latest[n] = Latest[n]\\ Latest[v]=\min_{<v,w>\in E} (Latest[w] - C_{v,w})
Latest[n]=Latest[n]Latest[v]=<v,w>∈Emin(Latest[w]−Cv,w)
上式就是求解最晚完成时间的递推公式，可以按照2.1节的思路编写代码，相比之下有这样几个点需要考虑：
L
a
t
e
s
t
[
i
]
0
≤
i
≤
N
−
1
Latest[i]_{0\le i \le N-1}
Latest[i]0≤i≤N−1的初始值怎么定
环路判断
代码如下（如果你不清除变量是什么意思，查阅最后的代码）：
/* 2.计算最迟时间 ********************************************************/
latest = vector<int>(num, sumMax);// 将所有终止点压入for(auto i =0; i < num; i++)if(!outDegree[i])
q.push(i);while(!q.empty()){auto index = q.front();
q.pop();for(auto&r : reverseData[index]){
latest[r.first]=min(latest[r.first], latest[index]- r.second);if(!--outDegree[r.first])
q.push(r.first);}}
2.3 求取机动时间
摘自《数据结构》P251
各顶点的最早和最晚完成时间被求出以后，能够很容易地确定在不影响工程进度的前提下，每一活动最多能耽误的时间长短。这个时间是否为
0
0
0 决定了该活动是否为关键路径。求
<
v
,
w
>
<v,w>
<v,w> 边上的允许耽误的最大时间
D
e
l
a
y
v
,
w
Delay_{v,w}
Delayv,w 采用的计算公式为：
D
e
l
a
y
v
,
w
=
L
a
t
e
s
t
[
w
]
−
E
a
r
l
i
e
s
t
[
v
]
−
C
v
,
w
Delay_{v,w} = Latest[w] - Earliest[v] - C_{v,w}
Delayv,w=Latest[w]−Earliest[v]−Cv,w
上式就是机动时间的求取公式。
2.4 输出问题
原题的输出描述比较难理解，实际上题目意思就是从所有的边中按照“输出要求”输出所有的关键路径。 输出要求：将一条边定义为
E
d
g
e
(
n
u
m
)
:
S
t
a
r
t
→
T
i
m
e
E
n
d
Edge(num):Start \xrightarrow[]{ Time } End\\
Edge(num):StartTimeEnd 上式中
n
u
m
num
num 输入的顺序，
S
t
a
r
t
Start
Start 为起点索引，
E
n
d
End
End 为终点索引，
T
i
m
e
Time
Time 为这条路径花费的时间。输出中
S
t
a
r
t
Start
Start 小者优先，如果
S
t
a
r
t
Start
Start相同，
n
u
m
num
num 大者优先。
