数据结构与算法 / 系统课时

依赖关系怎么求最早时间

依赖关系怎么求最早时间

当一组任务存在前置依赖时,最早完成时间不是把所有耗时相加,而是由最长的依赖链决定。本篇用 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 的开始时间。

DAG 上按拓扑顺序计算最早时间

为什么必须按拓扑顺序计算

动态规划的前提是:更新某个任务之前,它的所有前驱状态都已经确定。拓扑序正好保证每条依赖边都从序列前方指向后方,因此可以一次扫描完成状态传播,不需要反复松弛。

以 A -> B、A -> C、B -> D、C -> D 为例,若耗时分别为 3、2、4、2,则 B 最早在 3 时刻开始,C 也最早在 3 时刻开始;D 必须等待两者都完成,所以最早开始时间是 max(5, 7) = 7,最早完成时间为 9。

用拓扑动态规划计算总工期

下面的完整示例使用 Kahn 算法生成拓扑序,并在顶点出队时向后继传播最早时间。若最终处理的顶点数少于任务总数,说明图中存在环,此时不存在合法的依赖执行顺序。

python
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()))

预期输出

text
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 时间传播之外再加入调度约束。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

依赖关系怎么求最早时间

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通