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

== 算法步骤 ==
关键路径的计算分为以下步骤：
# '''拓扑排序'''：确定节点的处理顺序。
# '''正向计算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。