Python 算法：DAG 最长路径（基于拓扑排序）

# /*
# Python 算法：DAG 最长路径（基于拓扑排序）
# --------------------------------------------------------
# 原理概要：
# 在有向无环图（DAG）中，最长路径可使用拓扑排序后进行“反向松弛”得到。
# 与最短路径类似，但将松弛方向从 min → max。
#
# 基本步骤：
# 1) 对 DAG 进行拓扑排序；
# 2) 初始化 dist，所有节点为 -∞，起点设为 0；
# 3) 按拓扑序依次松弛所有边：
#       dist[v] = max(dist[v], dist[u] + w)
#
# 使用场景：
# - 寻找任务依赖中最长耗时路径；
# - 流程规划中的关键路径（Critical Path）；
# - 课程安排中最长前置路径。
#
# 注意：
# - 仅适用于 DAG，无环是前提；
# - DAG 最长路径不存在正权限制；
# - 比一般图的最长路径问题简单得多（一般情况 NP-hard）。
# */

# --------------------------------------------------------
from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    # 添加有向边 u -> v，权重 w
    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    # --------------------------------------------------------
    # 拓扑排序（Kahn）
    def topological_sort(self):
        indegree = defaultdict(int)

        # 统计入度
        for u in self.graph:
            for v, _ in self.graph[u]:
                indegree[v] += 1

        # 入度为 0 的节点
        queue = deque([u for u in self.graph if indegree[u] == 0])
        topo_order = []

        while queue:
            u = queue.popleft()
            topo_order.append(u)

            for v, _ in self.graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)

        return topo_order

    # --------------------------------------------------------
    # DAG 最长路径主算法
    def longest_path_dag(self, start):
        topo = self.topological_sort()

        # 初始化所有节点为负无穷
        dist = {node: float("-inf") for node in self.graph}
        dist[start] = 0

        # 按拓扑序松弛（max 方式）
        for u in topo:
            if dist[u] != float("-inf"):
                for v, w in self.graph[u]:
                    if dist[v] < dist[u] + w:
                        dist[v] = dist[u] + w

        return dist


# --------------------------------------------------------
# 示例图（DAG）
g = Graph()
g.add_edge("A", "B", 6)
g.add_edge("A", "C", 4)
g.add_edge("C", "B", 2)
g.add_edge("B", "D", 1)
g.add_edge("C", "D", 3)

# 执行最长路径
result = g.longest_path_dag("A")

# 输出结果
print("从 A 出发的最长路径：")
for node in result:
    print(node, ":", result[node])

# --------------------------------------------------------
# 输出示例（可能略有差异）：
# 从 A 出发的最长路径：
# A : 0
# C : 4
# B : 6
# D : 9
#
# 要点总结：
# - 必须是 DAG；
# - 采用拓扑排序；
# - 使用“最大松弛”公式；
# - 时间复杂度 O(V + E)；
# - 可用于关键路径分析（CPA）。
# */