关键路径（图论算法）

关键路径（Critical Path）是图论中用于项目管理的重要概念，特指在有向无环图（DAG）中完成项目所需的最长路径。该路径决定了项目的最短完成时间，路径上的任何延迟都会直接导致整个项目延期。关键路径方法（CPM）广泛应用于工程规划、软件开发等领域。

基本概念

关键路径分析基于以下术语：

• 活动（Activity）：项目中的具体任务，用有向边表示。
• 事件（Event）：活动的开始或结束时间点，用节点表示。
• 最早开始时间（Earliest Start Time, EST）：一个活动在不影响项目总工期的前提下可以开始的最早时间。
• 最晚开始时间（Latest Start Time, LST）：一个活动在不导致项目延期的情况下必须开始的最晚时间。
• 松弛时间（Slack）：LST与EST的差值，表示活动可延迟的时间。

关键路径是图中从起点到终点的最长路径，其上的所有活动松弛时间为零。

算法步骤

关键路径的计算分为以下步骤：

1. 拓扑排序：确定节点的处理顺序。
2. 正向计算EST：从起点出发，按拓扑序计算每个节点的最早开始时间。
3. 反向计算LST：从终点出发，按逆拓扑序计算每个节点的最晚开始时间。
4. 确定关键路径：筛选所有满足$EST=LST$的节点和边。

示例代码（Python）

以下代码演示如何计算关键路径：

from collections import defaultdict, deque

def critical_path(vertices, edges):
    # 拓扑排序
    in_degree = defaultdict(int)
    graph = defaultdict(list)
    time = {v: 0 for v in vertices}
    
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    
    queue = deque([v for v in vertices if in_degree[v] == 0])
    topo_order = []
    
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v, w in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 正向计算EST
    est = {v: 0 for v in vertices}
    for u in topo_order:
        for v, w in graph[u]:
            if est[v] < est[u] + w:
                est[v] = est[u] + w
    
    # 反向计算LST
    lst = {v: est[topo_order[-1]] for v in vertices}
    for u in reversed(topo_order):
        for v, w in graph[u]:
            if lst[u] > lst[v] - w:
                lst[u] = lst[v] - w
    
    # 提取关键路径
    critical_edges = []
    for u, v, w in edges:
        if est[u] == lst[u] and est[v] == lst[v] and est[v] - est[u] == w:
            critical_edges.append((u, v, w))
    
    return critical_edges

# 示例输入
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [
    ('A', 'B', 3), ('A', 'C', 2),
    ('B', 'D', 4), ('C', 'D', 1),
    ('D', 'E', 5), ('E', 'F', 2)
]

print(critical_path(vertices, edges))  # 输出: [('A', 'B', 3), ('B', 'D', 4), ('D', 'E', 5), ('E', 'F', 2)]

输出说明：关键路径为 A → B → D → E → F，总时长为 14。

实际应用案例

软件开发项目管理

假设开发一个功能模块包含以下任务： 1. 需求分析（3天） 2. 设计（2天） 3. 编码（5天） 4. 测试（2天） 5. 部署（1天）

依赖关系如下：

graph LR A[需求分析] --> B[设计] B --> C[编码] C --> D[测试] D --> E[部署]

关键路径为 需求分析 → 设计 → 编码 → 测试 → 部署，总时长 13 天。若编码延迟 2 天，则项目总时长变为 15 天。

数学表达

关键路径的总时长 $T$ 可表示为： $T=\underset{p\in \text{所有路径}}{\max }(\sum _{(u,v)\in p}w(u,v))$ 其中 $w(u,v)$ 是边 $(u,v)$ 的权重（即活动耗时）。

常见问题

• Q：图中存在多条关键路径怎么办？

 * A：若多条路径长度相同，则均为关键路径，需同时监控。

• Q：如何缩短关键路径？

 * A：通过并行化活动（如增加资源）或优化关键活动耗时。

总结

关键路径分析是优化项目进度的核心工具，适用于任何需要严格时间管理的场景。掌握其原理和实现方法，能有效提升对复杂项目的把控能力。