编辑“︁关键路径（图论算法）”︁

{{DISPLAYTITLE:关键路径（图论算法）}}

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

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

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

== 算法步骤 ==
关键路径的计算分为以下步骤：
# '''拓扑排序'''：确定节点的处理顺序。
# '''正向计算EST'''：从起点出发，按拓扑序计算每个节点的最早开始时间。
# '''反向计算LST'''：从终点出发，按逆拓扑序计算每个节点的最晚开始时间。
# '''确定关键路径'''：筛选所有满足<math>EST = LST</math>的节点和边。

=== 示例代码（Python） ===
以下代码演示如何计算关键路径：

<syntaxhighlight lang="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)]
</syntaxhighlight>

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

== 实际应用案例 ==
=== 软件开发项目管理 ===
假设开发一个功能模块包含以下任务：
1. 需求分析（3天）
2. 设计（2天）
3. 编码（5天）
4. 测试（2天）
5. 部署（1天）

依赖关系如下：
<mermaid>
graph LR
    A[需求分析] --> B[设计]
    B --> C[编码]
    C --> D[测试]
    D --> E[部署]
</mermaid>

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

== 数学表达 ==
关键路径的总时长 <math>T</math> 可表示为：
<math>
T = \max_{p \in \text{所有路径}} \left( \sum_{(u,v) \in p} w(u,v) \right)
</math>
其中 <math>w(u,v)</math> 是边 <math>(u,v)</math> 的权重（即活动耗时）。

== 常见问题 ==
* '''Q：图中存在多条关键路径怎么办？'''
  * A：若多条路径长度相同，则均为关键路径，需同时监控。
* '''Q：如何缩短关键路径？'''
  * A：通过并行化活动（如增加资源）或优化关键活动耗时。

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]