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

# /*
# Python 算法：DAG 最短路径（基于拓扑排序）
# --------------------------------------------------------
# 原理概要：
# 在有向无环图（DAG）中，可通过拓扑排序将节点按依赖顺序排好，
# 再对每个节点进行松弛操作，从而在线性时间 O(V + E) 内求得最短路径。
#
# 基本步骤：
# 1) 对图进行拓扑排序（Topological Sort）；
# 2) 初始化 dist，全设为正无穷，起点设为 0；
# 3) 按拓扑序依次松弛从当前节点发出的所有边；
# 4) 松弛公式：dist[v] = min(dist[v], dist[u] + w)
#
# 优势与适合场景：
# - 图必须无环；
# - 支持负权边（只要不形成环）；
# - 比 Dijkstra、Bellman-Ford 快；
# - 适合任务调度、课程依赖等天然无环结构。
# */

# --------------------------------------------------------
# 图结构：使用邻接表
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 shortest_path_dag(self, start):
        topo = self.topological_sort()
        dist = {node: float("inf") for node in self.graph}
        dist[start] = 0

        # 按拓扑排序依次松弛
        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)

# 执行 DAG 最短路径
distances = g.shortest_path_dag("A")

# 显示结果
print("从 A 出发的最短路径：")
for node in distances:
    print(node, ":", distances[node])

# --------------------------------------------------------
# 输出示例：
# 从 A 出发的最短路径：
# A : 0
# C : 4
# B : 6
# D : 7
#
# DAG 最短路径要点总结：
# - 必须是无环图；
# - 利用“拓扑排序 + 松弛”；
# - 时间复杂度 O(V + E)；
# - 可以处理负权边；
# */