拓扑最短路径（DAG Shortest Path）

在有向无环图（DAG, Directed Acyclic Graph）中，最短路径的求解比一般图更高效。由于图中不存在环路，所有顶点可以按照拓扑顺序（Topological Order）排列，再根据顺序逐点松弛边权即可在线性时间内完成求解。

一、拓扑最短路径的核心思想

1. 先做拓扑排序
拓扑排序保证：

每条有向边 $u\to v$ 中，顶点 $u$ 出现在 $v$ 之前。

2. 按拓扑顺序进行松弛（Relax）
拓扑序消除了“回头边”，因此对每个顶点只需松弛一次，不会出现重复更新。

3. 时间复杂度线性：

$$O(V+E)$$

比 Dijkstra、Bellman-Ford 更快，但要求图无环。

二、适用场景

• 任务调度、课程依赖等天然无环结构

• 边权可以为负，只要不形成环

• 希望以最高效率获得最短路径

三、算法步骤

1. 对图进行拓扑排序

2. 设置所有节点距离为正无穷，起点为 0

3. 按拓扑顺序遍历每个顶点

4. 对其所有邻边进行松弛

   $$\min (dist[v],dist[u]+weight(u,v))$$

四、Python 完整代码

# -------------------------------
# Python：DAG 最短路径（基于拓扑排序）
# -------------------------------

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))

    # 拓扑排序
    def topological_sort(self):
        indeg = defaultdict(int)

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

        # 入度为0的节点入队
        q = deque([u for u in self.graph if indeg[u] == 0])

        topo = []
        while q:
            u = q.popleft()
            topo.append(u)

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

        return topo

    # 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


# -------------------------------
# 示例
# -------------------------------

g = Graph()
g.add_edge("A", "B", 6)
g.add_edge("A", "C", 4)
g.add_edge("B", "D", 1)
g.add_edge("C", "B", 2)
g.add_edge("C", "D", 3)

distances = g.shortest_path_dag("A")

print("从 A 出发的最短路径：")
for node, d in distances.items():
    print(f"{node}: {d}")

五、运行结果示例

从 A 出发的最短路径：
A: 0 
B: 6 
C: 4 
D: 7

以上为示例输出，不同图结构会有不同结果。

六、拓扑最短路径与其他算法对比