元数据卡

• 前置知识：图遍历与搜索（前页）
• 预计时间：25 分钟
• 核心难度：进阶
• 完成标志：能解释 Dijkstra 为什么需要优先队列，知道 Bellman-Ford 怎么处理负权边，能用拓扑排序求 DAG 最短路径

---

你的进度

上一页你用 BFS 找到了无权图中的最短路径（边数最少）。但现在问题变了：森林里的兽道不再等长——有的路平坦（权重 2），有的路崎岖（权重 8），还有的捷径虽然短但只能单向走。从营地 A 到营地 E，哪条路的总权重最小？

A→B（6），B→E（2），A→C（3），C→D（1），D→E（1），D→B（1）

地图上 A 到 E 有两条路——A→B→E（总权重 8）和 A→C→D→E（总权重 5）。虽然 A→B→E 只有两步，但总权重更大。你要的不是"最少边数"，而是"最小总权重"。

这就是加权图的最短路径问题。

---

你的任务

学会三种加权最短路径算法：Dijkstra（无负权场景最优）、Bellman-Ford（可处理负权并检测负环）、以及面向 DAG 的拓扑排序最短路径法（O(V+E)，最快）。

---

破局 · 溯源

第一战：Dijkstra——贪心的里程碑

Dijkstra 算法帮你找从起点到所有其他节点的最短路径。核心思路：每次从"尚未确定最短距离"的节点中，选当前距离最小的那个——因为它不可能再被更短的路径更新了。

为什么这个推断成立？因为所有边权都非负。如果一个节点的当前距离已经是"候选人中最小的"，绕路走其他节点只会增加距离。

# Python: Dijkstra 最短路径
import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (距离, 节点)
    visited = set()

    while pq:
        dist, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

# 森林兽道图：A→B(6), A→C(3), B→E(2), C→D(1), D→E(1), D→B(1)
graph = {
    'A': [('B', 6), ('C', 3)],
    'B': [('E', 2)],
    'C': [('D', 1)],
    'D': [('E', 1), ('B', 1)],
    'E': []
}

result = dijkstra(graph, 'A')
for node, dist in sorted(result.items()):
    print(f"从 A 到 {node} 的最短距离: {dist}")

运行步骤：

1. 保存为 dijkstra.py
2. 运行 python3 dijkstra.py

预期输出：

从 A 到 A 的最短距离: 0
从 A 到 B 的最短距离: 5
从 A 到 C 的最短距离: 3
从 A 到 D 的最短距离: 4
从 A 到 E 的最短距离: 5

注意 A→B 的最短距离是 5（走 A→C→D→B = 3+1+1=5），而不是直走 A→B 的 6。Dijkstra 帮你找到了明明"不走直线却更短"的路线。

Dijkstra 执行过程（手动模拟）：

初始: distances = {A:0, B:inf, C:inf, D:inf, E:inf}, pq = [(0,A)]

1. pop (0,A), 处理邻居 B(6), C(3)
   distances: {A:0, B:6, C:3, D:inf, E:inf}, pq = [(3,C), (6,B)]

2. pop (3,C), 处理邻居 D(1) → D = 4
   distances: {A:0, B:6, C:3, D:4, E:inf}, pq = [(4,D), (6,B)]

3. pop (4,D), 处理邻居 E(1)→E=5, B(1)→B=5(更新! 6→5)
   distances: {A:0, B:5, C:3, D:4, E:5}, pq = [(5,B), (5,E), (6,B)]

4. pop (5,B), B 已访问, 跳过
5. pop (5,E), 处理邻居(无)
6. pop (6,B), B 已访问, 跳过 → pq = []

---

深入：为什么 Dijkstra 不能处理负权边？

因为负权边会破坏"当前距离最小的节点不会再被更新"这个假设。看这个例子：

A→B（3），A→C（4），C→B（-2）

起点 A 走 A→B 距离 3，B 被标记为"已确认"。但后来发现 A→C→B 距离 4+(-2)=2，比 3 小——可 B 已经被标记为"最终距离"了，不会再被更新。结果错了。

如果图里只有非负权边，Dijkstra 是最优选择。有负权边时，你需要 Bellman-Ford。

---

第二战：Bellman-Ford——相信重复的力量

Bellman-Ford 的思路暴力但可靠：对所有边做 V-1 次"松弛"（检查走这条边能不能让目标节点的距离更短），如果第 V 次还能松弛就说明存在负权环。

# Python: Bellman-Ford 最短路径
def bellman_ford(edges, num_nodes, start):
    # edges: [(u, v, weight), ...]
    distances = [float('inf')] * num_nodes
    distances[start] = 0

    # V-1 轮松弛
    for i in range(num_nodes - 1):
        updated = False
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                updated = True
        if not updated:
            print(f"第{i+1}轮后提前终止")
            break

    # 第 V 轮：检测负环
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            raise ValueError("图中存在负权环，无法计算最短路径")

    return distances

# 同上的图（用边列表表示）
# 节点索引: 0=A, 1=B, 2=C, 3=D, 4=E
edges = [
    (0, 1, 6),  # A→B
    (0, 2, 3),  # A→C
    (1, 4, 2),  # B→E
    (2, 3, 1),  # C→D
    (3, 4, 1),  # D→E
    (3, 1, 1),  # D→B
]

result = bellman_ford(edges, 5, 0)
node_names = ['A', 'B', 'C', 'D', 'E']
for i, dist in enumerate(result):
    print(f"从 A 到 {node_names[i]} 的最短距离: {dist}")

运行步骤：

1. 保存为 bellman_ford.py
2. 运行 python3 bellman_ford.py

预期输出：

第3轮后提前终止
从 A 到 A 的最短距离: 0
从 A 到 B 的最短距离: 5
从 A 到 C 的最短距离: 3
从 A 到 D 的最短距离: 4
从 A 到 E 的最短距离: 5

和 Dijkstra 的输出一致。但对 Bellman-Ford 来说，即使有负权边（只要没负权环），结果依然正确。

松弛过程（V=5, 最多 4 轮）：

初始: distances = [0, inf, inf, inf, inf]
第1轮: [0, 6, 3, inf, inf]     (A→B=6, A→C=3)
第2轮: [0, 5, 3, 4, inf]       (D→B=3+1=4 → B从6更新为5; C→D=3+1=4)
第3轮: [0, 5, 3, 4, 5]         (D→E=4+1=5; 没有其他更新)
第4轮: 没有任何更新 → 提前终止

对比	Dijkstra	Bellman-Ford
时间复杂度	O((V+E) log V)	O(V x E)
负权处理	不支持	支持
负环检测	无法	可以（第 V 轮检测）
实现复杂度	中等（优先队列）	简单（双重循环）
适用场景	无负权加权图（默认选择）	有负权 / 需要环检测

Bellman-Ford 不是比 Dijkstra "更好"，只是更通用。但它的 O(V x E) 在稀疏大图上非常慢——1 万节点 5 万条边，Dijkstra 几毫秒，Bellman-Ford 要跑几秒。

---

第三战：DAG 最短路径——拓扑排序前来助阵

如果图是有向无环图（DAG），可以用拓扑排序 + 动态规划在 O(V+E) 时间内找出最短路径——比 Dijkstra 和 Bellman-Ford 都快。

原理：按拓扑序处理节点。每个节点的最短距离被确定后，用它更新所有邻居的距离。拓扑序保证处理一个节点时，它前面所有节点的距离已经固定了。

# Python: DAG 最短路径（拓扑排序 + DP）
from collections import deque

def dag_shortest_path(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    # 1. 计算入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor, _ in graph[node]:
            in_degree[neighbor] += 1

    # 2. Kahn 拓扑排序
    queue = deque([node for node in graph if in_degree[node] == 0])
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor, _ in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 3. 按拓扑序更新最短距离
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    for node in topo_order:
        if distances[node] != float('inf'):
            for neighbor, weight in graph[node]:
                new_dist = distances[node] + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist

    return distances, topo_order

# 课程依赖 DAG
# 0: 微积分（无依赖）
# 1: 线性代数（依赖 0，1 学期）
# 2: 概率论（依赖 1，1 学期）
# 3: 机器学习（依赖 1、2，2+1 学期）
# 4: Python 基础（无依赖）
# 5: 深度学习（依赖 3、4，2+1 学期）
dag = {
    0: [(1, 1)],        # 微积分→线代
    1: [(2, 1), (3, 2)],  # 线代→概率, 线代→ML
    2: [(3, 1)],        # 概率→ML
    3: [(5, 2)],        # ML→深度学习
    4: [(5, 1)],        # Python→深度学习
    5: []
}

distances, topo = dag_shortest_path(dag, 0)
course_names = {0: "微积分", 1: "线性代数", 2: "概率论",
                3: "机器学习", 4: "Python", 5: "深度学习"}
print(f"拓扑序: {[course_names[i] for i in topo]}")
for node, dist in sorted(distances.items()):
    label = course_names[node]
    if dist != float('inf'):
        print(f"{label}: 最早 {dist} 学期后可选")
    else:
        print(f"{label}: 从微积分出发不可达")

运行步骤：

1. 保存为 dag_shortest.py
2. 运行 python3 dag_shortest.py

预期输出：

拓扑序: ['微积分', 'Python', '线性代数', '概率论', '机器学习', '深度学习']
微积分: 最早 0 学期后可选
线性代数: 最早 1 学期后可选
概率论: 最早 2 学期后可选
机器学习: 最早 3 学期后可选
深度学习: 最早 5 学期后可选
Python: 从微积分出发不可达

Python 基础（节点 4）从微积分出发没有路径可达，所以距离是 inf。而深度学习需要同时满足 ML（距微积分 3 学期）和 Python（不可达）——但从微积分到 ML 再 +2 = 5 学期。

按拓扑序更新的过程：

拓扑序: 0→4→1→2→3→5
处理 0（微积分）: distances[1]=1, distances[4]=inf(跳过,不在0的邻居中)
处理 4（Python）: 从0不可达, 跳过
处理 1（线性代数）: distances[2]=1+1=2, distances[3]=1+2=3
处理 2（概率论）: distances[3]=min(3, 2+1=3)=3
处理 3（机器学习）: distances[5]=3+2=5
处理 5（深度学习）: 无出边

注意拓扑序的正确性：微积分（无依赖）在 Python 之前或之后都不影响——拓扑排序结果不唯一，但每条依赖边都保证方向正确。

---

三种算法对比

算法	时间复杂度	负权	负环	特殊前提
Dijkstra	O((V+E) log V)	不支持	无	所有边权非负
Bellman-Ford	O(V x E)	支持	可检测	无负环
DAG 拓扑 DP	O(V+E)	支持	DAG 无环	必须是有向无环图

选择法则：无负权选 Dijkstra，有负权未知选 Bellman-Ford，确定是 DAG 就用拓扑 DP。

---

常见陷阱

• Dijkstra 遇到负权崩了：一旦节点被标记为"已确认"，它不会再回头检查。负权导致已确认的距离可能不是最优的。不是算法实现的问题，是前提条件不满足。
• Bellman-Ford 慢是真的慢：不要因为 Bellman-Ford 能处理负权就默认用它。Dijkstra 在无负权图上快一个数量级。
• DAG 不代表一定有拓扑序：DAG 一定有拓扑序，但你的图可能不是 DAG 而你以为它是。如果图中有环，拓扑排序会检测失败（结果长度 != 节点数）。

---

旅人笔记

加权最短路径三件套：Dijkstra（优先队列、无负权默认选）、Bellman-Ford（双重循环、可负权能查环）、DAG 拓扑 DP（线性时间、最快但限制最多）。三选一的关键是知道你的图长什么样。

下一步

图的核心算法告一段落。排序——所有算法的基础操作，但你还没有系统地看过各种排序策略。

看第9章：排序 ->