8.3 加权最短路径：路少，不等于路程短

第 8 章 · 加权最短路径｜前置：BFS 与 DFS、堆和拓扑排序。本页用一套统一接口比较 Dijkstra、Bellman–Ford 与 DAG 拓扑松弛，并保留前驱以还原路径。

比较边权之和

把每条边的耗时写进图以后，只数边就不够了。A 到 E 有两条候选路：

A → B → E        6 + 2 = 8
A → C → D → E    3 + 1 + 1 = 5

第二条路多一条边，总耗时反而更小。本节最小化的是边权之和。

1. 所有边权都非负：Dijkstra。
2. 可能有负权：Bellman–Ford。
3. 已知是 DAG：按拓扑序松弛，可含负权。

负权不是“物理距离为负”，可以是返利、能量回收或汇率收益。负权环若能从起点到达，绕一圈成本还会下降。环上以及从环可达的顶点，其最短值没有下界；其他顶点的最短值不一定受影响。本页 Bellman–Ford 一旦发现这种环就抛错，不部分返回结果。

一份统一、可执行的实现

顶点可以是可哈希对象，包括 None，但应有自反、稳定的相等关系和稳定哈希。Dijkstra 的堆条目带唯一递增序号，距离相同时无需比较顶点对象。三个算法返回 distance 与 parent：距离映射含所有输入顶点，不可达者为 inf；前驱映射只含可达顶点，起点指向自身。reconstruct_path 对未知或不可达目标返回 None。

示例限定整数权重，比较前拒绝浮点数、NaN 和无穷值。这样 Python 的大整数加法不会溢出，也能精确判断松弛与负环；分数成本可先换算成整数单位。改为浮点权重时，需要另行处理舍入、溢出和负环判断误差。

Dijkstra 与 DAG 输入是 {顶点: [(邻居, 权重), ...]}，会补齐仅作为终点出现的顶点；Bellman–Ford 使用显式顶点列表和 (起点, 终点, 权重) 边列表，缺失端点会报错。重复边允许保留，无向边需录入两个方向。三者都复制输入容器，输入迭代器会被消耗。

from collections import deque
from itertools import count
import heapq
import math

def _require_weight(weight):
    if not isinstance(weight, int):
        raise TypeError("edge weight must be an integer")

def _weighted_adjacency(graph):
    adjacency = {node: list(edges) for node, edges in graph.items()}
    for edges in list(adjacency.values()):
        for neighbor, weight in edges:
            _require_weight(weight)
            adjacency.setdefault(neighbor, [])
    return adjacency

def reconstruct_path(parent, start, target):
    if start not in parent or target not in parent:
        return None
    path = []
    current = target
    seen = set()
    while current in parent:
        if current in seen:
            raise ValueError("parent map contains a cycle")
        seen.add(current)
        path.append(current)
        if current == start:
            path.reverse()
            return path
        current = parent[current]
    return None

def dijkstra(graph, start):
    """所有边权非负时的单源最短路。"""
    adjacency = _weighted_adjacency(graph)
    if start not in adjacency:
        raise KeyError(f"unknown start vertex: {start!r}")
    for edges in adjacency.values():
        for _, weight in edges:
            if weight < 0:
                raise ValueError("Dijkstra requires non-negative edge weights")

    distance = {node: math.inf for node in adjacency}
    parent = {start: start}
    distance[start] = 0
    sequence = count()
    heap = [(0, next(sequence), start)]

    while heap:
        known_distance, _, node = heapq.heappop(heap)
        if known_distance != distance[node]:
            continue
        for neighbor, weight in adjacency[node]:
            candidate = known_distance + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                parent[neighbor] = node
                heapq.heappush(heap, (candidate, next(sequence), neighbor))
    return distance, parent

def bellman_ford(nodes, edges, start):
    """检测且仅检测从 start 可达的负权环。"""
    nodes = list(dict.fromkeys(nodes))
    node_set = set(nodes)
    if start not in node_set:
        raise KeyError(f"unknown start vertex: {start!r}")
    edges = list(edges)
    for source, target, weight in edges:
        _require_weight(weight)
        if source not in node_set or target not in node_set:
            raise KeyError("edge endpoint is missing from nodes")

    distance = {node: math.inf for node in nodes}
    parent = {start: start}
    distance[start] = 0

    for _ in range(max(0, len(nodes) - 1)):
        changed = False
        for source, target, weight in edges:
            if distance[source] == math.inf:
                continue
            candidate = distance[source] + weight
            if candidate < distance[target]:
                distance[target] = candidate
                parent[target] = source
                changed = True
        if not changed:
            break

    for source, target, weight in edges:
        if distance[source] != math.inf:
            if distance[source] + weight < distance[target]:
                raise ValueError("reachable negative-weight cycle")
    return distance, parent

def dag_shortest_paths(graph, start):
    """DAG 单源最短路；拓扑排序失败即拒绝输入。"""
    adjacency = _weighted_adjacency(graph)
    if start not in adjacency:
        raise KeyError(f"unknown start vertex: {start!r}")

    indegree = {node: 0 for node in adjacency}
    for edges in adjacency.values():
        for neighbor, _ in edges:
            indegree[neighbor] += 1
    queue = deque(node for node in adjacency if indegree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor, _ in adjacency[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    if len(order) != len(adjacency):
        raise ValueError("DAG shortest paths requires an acyclic graph")

    distance = {node: math.inf for node in adjacency}
    parent = {start: start}
    distance[start] = 0
    for node in order:
        if distance[node] == math.inf:
            continue
        for neighbor, weight in adjacency[node]:
            candidate = distance[node] + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                parent[neighbor] = node
    return distance, parent

if __name__ == "__main__":
    roads = {
        "A": [("B", 6), ("C", 3)],
        "B": [("E", 2)],
        "C": [("D", 1)],
        "D": [("E", 1), ("B", 1)],
        "E": [],
        "Z": [],
    }
    distance, parent = dijkstra(roads, "A")
    print(distance)
    print(reconstruct_path(parent, "A", "E"))

预期核心输出为：

{'A': 0, 'B': 5, 'C': 3, 'D': 4, 'E': 5, 'Z': inf}
['A', 'C', 'D', 'E']

Dijkstra：为什么贪心成立

从 A 出发，先知道 B 的候选距离 6、C 的候选距离 3。优先队列先取 C，再由 C 把 D 更新为 4；D 又把 B、E 都更新为 5。

确定 A=0  -> B=6, C=3
确定 C=3  -> D=4
确定 D=4  -> B=5, E=5
确定 E=5
确定 B=5  -> E 仍为 5

当边权都非负时，尚未确定的路线只会让成本保持或增加，所以堆顶候选可以定案。代码没有用 visited 永久封闭节点，而是跳过“距离已过期”的堆条目，这是常见的优先队列实现。

负权会破坏这个证明。为了让失败尽早且一致，本实现先扫描整张输入图；即使负边位于起点不可达区域，也拒绝 Dijkstra。Python heapq 是最小堆接口，详见 Python heapq。

本实现会保留陈旧堆条目，一条边最多成功松弛一次，但同一顶点可能在堆中出现多次。堆大小上界为 O(E+1)，不能直接按 O(V) 计。包含输入复制和全图检查后，时间上界为 O(V + E log(E+2))，额外空间为 O(V+E)，其中已包含邻接副本、距离/前驱映射和堆。对无平行边的简单图，E <= V²，才可进一步写成常见的 O((V+E) log(V+1))。这些计数假定哈希访问平均为常数，整数加法与比较的位数成本另计。

Bellman–Ford：重复松弛

对边 u → v (w)，若 distance[u] + w < distance[v]，就更新 v。一条不含环的简单最短路至多有 V-1 条边，因此最多做 V-1 轮；某轮完全没更新即可提前结束。

再扫一轮，如果仍可更新，而且 u 从起点可达，就存在可达负权环。注意检测范围：

• 本函数不会报告与起点断开的负权环。
• 若需求是“整张图有没有负权环”，可以添加一个权重为 0、连向所有顶点的超级源点，再运行检测。

官方文档也区分了单源可达负环与不在源点分量中的负环：NetworkX Bellman–Ford。

每轮最多扫描 E 条边，共至多 V-1 轮再加一次检查。计入 V 个顶点的初始化，时间上界为 O(V(E+1))，通常在 E>0 时简称 O(VE)；边列表副本、集合和返回映射占 O(V+E) 空间。它能处理负边，但不应因为“更通用”就默认替代 Dijkstra。

DAG：按依赖顺序松弛一次

DAG 有拓扑序。所有进入 u 的边都处理完后再处理 u，每条边只需松弛一次，所以时间是 O(V + E)，并且允许负权。计入邻接副本，额外空间也是 O(V+E)。代码会验证拓扑排序是否覆盖所有顶点，任何区域出现有向环都会被拒绝，即使该区域从起点不可达。

课程依赖不一定是最短路问题

课程依赖图适合解释拓扑顺序，却不一定适合解释“最早第几学期修完”：

• 最短路径选择一条总权重最小的依赖链。
• 所有先修课都必须完成时，完成时间通常由最长的先修链或更完整的调度模型决定。

因此，若一门课同时依赖“机器学习”和“Python”，DAG 最短路只说明从某个起点到它的最便宜路径，不能自动证明所有先修条件何时满足。这个区别比记住一段代码更重要。

三种算法速查

算法	边权条件	负环	时间
BFS	无权或等非负权	不适用	O(V + E)
本页 Dijkstra + 惰性二叉堆	非负	不处理	O(V + E log(E+2))
Bellman–Ford	可有负权	检测起点可达负环	O(V(E+1))
DAG 拓扑松弛	可有负权，必须无环	输入有环即拒绝	O(V + E)

更完整的算法入口与复杂度对照见 NetworkX shortest paths。

排错清单

• Dijkstra 前是否验证了所有边权非负？
• 堆中距离相等时，顶点对象是否会被拿来比较？
• 邻居只出现在边的终点时，是否仍进入结果映射？
• Bellman–Ford 是否只从有限距离的 u 松弛？
• 负环是全图检测，还是 source-reachable / 起点可达检测？
• DAG 算法是否真的验证了无环？
• 输出只有距离，还是也保留了路径前驱？
• 不可达目标返回 None，还是空列表？API 必须固定。

走出加权路网

最短路径算法的选择由输入前提决定：非负边权允许 Dijkstra 贪心定案；一般含负权图可用 Bellman–Ford，并明确只检测起点可达的负环；若已知是 DAG，则可按拓扑序让每条边只松弛一次。小图上逐轮写下距离与前驱，比背三段模板更容易暴露错误前提。

图算法到这里暂告一段落。下一章转向排序，比较同一批元素在不同策略下怎样安排比较与移动：第 9 章：基础排序。