数据结构与算法 / 系统课时
依赖关系怎么求最早时间
依赖关系怎么求最早时间
当一组任务存在前置依赖时,最早完成时间不是把所有耗时相加,而是由最长的依赖链决定。本篇用 DAG 上的拓扑动态规划,计算每个任务的最早开始、最早完成时间,并识别决定总工期的关键依赖链。
学习目标
- 理解为什么最早完成时间等价于 DAG 上的最长路径问题。
- 能按拓扑顺序更新每个任务的最早开始与完成时间。
- 能识别环依赖,并理解它为什么使时间计算失效。
从依赖图定义时间状态
把每个任务看成一个顶点,前置关系 u -> v 表示任务 v 必须等待 u 完成。设任务 v 的耗时为 duration[v],则它的最早开始时间取所有直接前驱最早完成时间的最大值;没有前驱的任务可以从时间 0 开始。
因此可以维护两个状态:earliest_start[v] 表示任务最早开始时间,earliest_finish[v] = earliest_start[v] + duration[v]。对每条边 u -> v,只要 u 已经处理完,就可尝试用 earliest_finish[u] 更新 v 的开始时间。

为什么必须按拓扑顺序计算
动态规划的前提是:更新某个任务之前,它的所有前驱状态都已经确定。拓扑序正好保证每条依赖边都从序列前方指向后方,因此可以一次扫描完成状态传播,不需要反复松弛。
以 A -> B、A -> C、B -> D、C -> D 为例,若耗时分别为 3、2、4、2,则 B 最早在 3 时刻开始,C 也最早在 3 时刻开始;D 必须等待两者都完成,所以最早开始时间是 max(5, 7) = 7,最早完成时间为 9。
用拓扑动态规划计算总工期
下面的完整示例使用 Kahn 算法生成拓扑序,并在顶点出队时向后继传播最早时间。若最终处理的顶点数少于任务总数,说明图中存在环,此时不存在合法的依赖执行顺序。
from collections import deque
durations = {
"A": 3,
"B": 2,
"C": 4,
"D": 2,
}
edges = [
("A", "B"),
("A", "C"),
("B", "D"),
("C", "D"),
]
graph = {task: [] for task in durations}
indegree = {task: 0 for task in durations}
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
queue = deque(task for task in durations if indegree[task] == 0)
earliest_start = {task: 0 for task in durations}
earliest_finish = {task: durations[task] for task in durations}
processed = 0
while queue:
u = queue.popleft()
processed += 1
# u 已经满足全部前置条件,可以把完成时间传播给后继。
earliest_finish[u] = earliest_start[u] + durations[u]
for v in graph[u]:
earliest_start[v] = max(
earliest_start[v],
earliest_finish[u],
)
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
if processed != len(durations):
raise ValueError("dependency graph contains a cycle")
for task in durations:
print(
task,
"start=", earliest_start[task],
"finish=", earliest_finish[task],
)
print("project_finish=", max(earliest_finish.values()))预期输出
A start= 0 finish= 3
B start= 3 finish= 5
C start= 3 finish= 7
D start= 7 finish= 9
project_finish= 9最长依赖链决定总完成时间
如果只关心整个项目最早何时结束,答案就是所有任务 earliest_finish 的最大值。它对应某条从源任务到结束任务的最长依赖链;链上任一任务延迟,都会直接推迟总工期,因此也常被称为关键路径。
若还需要恢复具体关键链,可以在每次 earliest_start[v] 被更大值更新时,同时记录使它取得最大值的前驱。计算结束后从最晚完成的任务沿前驱反向追踪,即可得到决定当前总工期的依赖链。
这套方法适合构建流水线、课程先修关系、工程任务排期等“前置任务全部完成后才能开始”的场景;若任务还受资源容量、并行槽位或工作日历限制,则需要在 DAG 时间传播之外再加入调度约束。