08 · 最短路径与最小生成树（Shortest Path & Minimum Spanning Tree）

📅 预计 120 分钟　|　⭐ 本章主题：图上的两大经典优化问题——「点到点最省钱」和「全图连起来最省钱」

---

8.0 从导航和布线说起

两个场景，两个经典问题：

• 导航：从家到学校，路线很多，找总距离最短的那条——这是最短路径问题（shortest path）。
• 布线 / 修路：要把 N 个村庄全部通上电，电线怎么拉总成本最低——这是最小生成树问题（minimum spanning tree, MST）。

它们长得像，但目标完全不同：最短路径求「两点之间」的最优，最小生成树求「连接全部点」的最优。本章两个主角，外加两套工具（优先队列、并查集）。

---

8.1 最短路径问题总览

按「起点数」和「边权符号」分四类：

问题	起点	边权要求	算法	复杂度
单源最短路径	一个起点	非负权	Dijkstra	O((V+E)log V)
单源最短路径	一个起点	允许负权	Bellman-Ford	O(VE)
多源最短路径	所有点对	可有负权（无负环）	Floyd-Warshall	O(V³)
多源最短路径	所有点对	边权都非负	多次 Dijkstra	O(V·(V+E)log V)

术语：单源（single source）是一个起点到所有点；多源是任意两点之间。还有几个必须记的结论：

• 若图里有负权环（一个环的总权为负），最短路径无意义（可以无限绕圈变小），Bellman-Ford 能检测出来。
• Dijkstra 对负权会失效，不是不够快，而是它的贪心基础被打破。

---

8.2 Dijkstra：单源 · 非负权 ⭐

贪心的「朋友圈扩散」

Dijkstra（迪杰斯特拉）是贪心算法：维护一个「已确定最短路径」的集合，每次从没确定的点里挑当前距离最小的那个，用它的邻居去松弛（relax）——即尝试通过它让邻居的路径变短。关键在于：边权非负时，当前距离最小的未确定点，其距离已经不可能再被改短，可以放心收进集合。

用**优先队列（堆）**实现，每次 O(log V) 取最小，复杂度 O((V+E)log V)。

import heapq

def dijkstra(graph, start):
    # graph: {顶点: [(邻居, 权重), ...]}
    dist = {v: float("inf") for v in graph}
    dist[start] = 0
    pq = [(0, start)]                 # 小顶堆：距离越小越先出
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:               # 这条记录过期了（已被更短路径更新过）
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:          # 松弛成功：发现一条更短的到 v 的路
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("A", 1), ("C", 2), ("D", 5)],
    "C": [("A", 4), ("B", 2), ("D", 1)],
    "D": [("B", 5), ("C", 1)],
}
print(dijkstra(graph, "A"))
# 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
# 解释: A→B=1；A→B→C=1+2=3（比直达 4 短）；A→B→C→D=3+1=4

if d > dist[u]: continue 这行是「过期记录」处理：堆里可能残留旧距离，出堆时发现比当前记录还大，直接扔掉。

为什么负权会失效：Dijkstra 假设「当前距离最小的点以后不会变短」。但若存在负权边，一个「已经确定」的点可能被更后面的一条负边路径反超。比如 A→B 权重 5、A→C 权重 2、C→B 权重 -3，B 会被先确定成 5，但实际最短是 2 + (-3) = -1，错过了。

⚠️ 常见错误

1. 没用 continue 跳过过期记录：旧记录反复出堆，可能死循环或结果错误。
2. 负权图硬用 Dijkstra：会得到错解；负权用 Bellman-Ford。
3. 图不连通：无法到达的点距离保持 inf，输出前要处理（或明确说明）。
4. 记录路径时只记距离不记前驱：如果要求输出具体路径，需要额外用 prev 数组记录「从哪来的」。

---

8.3 Bellman-Ford：单源 · 可负权

把所有边反复「松弛」n-1 轮

Bellman-Ford（贝尔曼-福特）思想极朴素：最短路径经过的边数最多 n-1 条（否则成环，环可去掉），所以把所有边整体松弛一遍，重复 n-1 轮。每轮至少有一个顶点的最短距离被确定下来。第 n 轮如果还能松弛，说明存在负权环。

def bellman_ford(edges, n, start):
    # edges: [(u, v, w)]，顶点编号 0..n-1
    dist = [float("inf")] * n
    dist[start] = 0
    for _ in range(n - 1):                     # 最多 n-1 轮
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:          # 松弛
                dist[v] = dist[u] + w
                updated = True
        if not updated:                        # 这轮没更新，提前结束
            break
    for u, v, w in edges:                      # 再松弛一轮检测负环
        if dist[u] + w < dist[v]:
            return None                        # 负权环，最短路径不存在
    return dist

edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 2)]
print(bellman_ford(edges, 4, 0))
# 输出: [0, 4, 1, 3]
# 解释: 0→1=4；0→1→2=4-3=1（比直达 5 短）；0→1→2→3=1+2=3

复杂度 O(VE)，比 Dijkstra 慢，但能处理负权、还能检测负环。适合「边少、可能有负权」的场景，也是差分约束系统的底子。

⚠️ 常见错误

1. 忘了第 n 轮检测负环：只松弛 n-1 轮不检测，负环问题就漏了。
2. 把 dist[u] + w < dist[v] 写成 <=：遇到负权环时判断会不稳定，通常用严格小于。
3. n-1 轮写成 n 轮：多一轮多数实现仍正确，但要有意识：n 条边的路径必然含环。
4. 误以为 Bellman-Ford 能处理负环图：它只能检测负环，有负环时结果无意义。

---

8.4 Floyd-Warshall：多源 · 动态规划

三重循环，把所有「中间点」试一遍

Floyd-Warshall（弗洛伊德）是多源最短路径的教科书算法，用动态规划：dist[i][j] 表示 i 到 j 的最短距离，外层循环枚举「中间点 k」，尝试「i→k→j」是否比「i→j」更短。三重循环 O(V³)，代码短到可以背。

def floyd(graph, n):
    # graph: n×n 矩阵，graph[i][j] = 直接边权重，无边为 INF，i==j 为 0
    dist = [row[:] for row in graph]           # 拷贝一份，不污染原数据
    for k in range(n):                          # 中间点
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

INF = float("inf")
graph = [
    [0, 3, INF, 7],
    [3, 0, 2, INF],
    [INF, 2, 0, 1],
    [7, INF, 1, 0],
]
for row in floyd(graph, 4):
    print(row)
# 输出:
# [0, 3, 5, 6]
# [3, 0, 2, 3]
# [5, 2, 0, 1]
# [6, 3, 1, 0]
# 例: 0→2 最短是 0→1→2 = 3+2 = 5，不是直达（INF）

三点必须说清：

• k 必须放最外层。放内层会出错，因为 dist[i][k] 里的 k 是变动的中间点，需要按 k 从小到大把所有经 k 中转的情况先处理完。
• 支持负权边，但不允许负权环（有负环则对角线上会出现负数，可用来检测）。
• dist[i][i] 恒为 0；若算法结束后某 dist[i][i] < 0，说明存在负环。

⚠️ 常见错误

1. 循环顺序写错：k 不在最外层，或 i、j 在 k 外层，结果错误。
2. INF 参与加法溢出：Python 的 inf + 1 仍是 inf，不报错；但在别的语言里 INF + w 可能溢出，需先判断 dist[i][k] 是否为 INF。
3. 忘记对角初始化为 0：不把 dist[i][i] 初始化为 0，对角会被算成绕圈路径。
4. V 太大还用 Floyd：O(V³)，V=1000 时是 10 亿次操作，Python 会很慢；点少（≤300）或稠密图才合适。

---

8.5 最短路径三兄弟对比

算法	起点	边权	负环检测	复杂度	选它的情况
Dijkstra	单源	非负	无	O((V+E)log V)	一般默认首选
Bellman-Ford	单源	可负	能	O(VE)	有负权边
Floyd-Warshall	多源	可负（无负环）	能	O(V³)	要任意两点距离、点少

记忆：非负、单源 → Dijkstra；有负权 → Bellman-Ford；要全点对 → Floyd。

---

8.6 最小生成树问题

用最少的边，把整张图连起来

生成树（spanning tree）：包含全部 n 个顶点的树（恰好 n-1 条边，且连通、无环）。最小生成树（MST）是所有生成树里边权和最小的那棵。

两个核心性质：

• 切割性质（cut property）：把顶点集切成两半（任何切法），跨越这条切割的所有边里权最小的一条，一定在某个 MST 里。
• 回路性质（cycle property）：任何一个环里权最大的边，一定不在 MST 里（除非并列）。

Prim 和 Kruskal 分别是这两种性质的具体化。还要记住：MST 可能不唯一（当有等权边时），但总权值唯一。n 个顶点 m 条边的连通图，MST 一定有且只有 n-1 条边。

---

8.7 Prim：从一个点「长」出去 ⭐

贪心 + 切割性质

Prim 从任意一个点出发，维护「已加入的顶点集合」，每次从「横跨内外两个集合的边」里挑一条权最小的边加入，并把对应顶点纳入集合，重复 n-1 次。实现和 Dijkstra 长得几乎一样（也是堆），区别只在：Dijkstra 的键是「到起点的距离」，Prim 的键是「到当前树的距离」。

import heapq

def prim(graph, n, start=0):
    # graph: 邻接表 {u: [(邻居, 权重)]}，顶点编号 0..n-1
    visited = [False] * n
    pq = [(0, start)]                     # (到树的距离, 顶点)
    total, cnt = 0, 0
    while pq:
        w, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        cnt += 1
        for v, wv in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (wv, v))
    return total if cnt == n else None    # 图不连通则无生成树

graph = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 3), (3, 8)],
    2: [(1, 3), (3, 5)],
    3: [(0, 6), (1, 8), (2, 5)],
}
print(prim(graph, 4))
# 输出: 10   （选 0-1=2, 1-2=3, 2-3=5，共 10）

复杂度：堆实现 O((V+E)log V)；稠密图用朴素 O(V²) 实现反而更快。起点选哪个都行，结果总权值一样。

⚠️ 常见错误

1. 把 Prim 的距离键写成 Dijkstra 的「到起点距离」：Prim 要的是「到树的最小边」，两者只在非负权下代码近似，语义完全不同。
2. 堆里混入过期的旧边：同 Dijkstra，要 if visited[u]: continue。
3. 图不连通：cnt 到不了 n，返回 None；别当 0 处理。

---

8.8 Kruskal：把所有边排序，从小加 ⭐

并查集 + 回路性质

Kruskal 思路极直观：把所有边按权重从小到大排序，一条条尝试加入。只要这条边的两个端点还不在一棵树上（加入不会成环），就选它；否则跳过。判断「两个点是否已连通」以及「把两棵树合并」需要并查集（union-find）。

def find(parent, x):
    while parent[x] != x:                 # 找根，顺手路径压缩
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return False                      # 已经在同一棵树上，加这条边会成环
    parent[ra] = rb
    return True

def kruskal(edges, n):
    parent = list(range(n))
    edges.sort(key=lambda e: e[2])        # 按权重升序
    total, cnt = 0, 0
    for u, v, w in edges:
        if union(parent, u, v):
            total += w
            cnt += 1
            if cnt == n - 1:              # 选够 n-1 条边就完成
                break
    return total if cnt == n - 1 else None

edges = [(0, 1, 2), (1, 2, 3), (2, 3, 5), (0, 3, 6), (1, 3, 8)]
print(kruskal(edges, 4))
# 输出: 10   依次选 (0,1,2) (1,2,3) (2,3,5)，跳过成环的边

并查集是个独立的常用数据结构，三句话讲清：

• find(x) 返回 x 所在集合的「代表」（根），顺带路径压缩让后续查找几乎 O(1)。
• union(a, b) 把两个集合合并。
• 用「是否同根」判断两点是否已连通。

排序 O(E log E) + 并查集操作近似 O(E·α)，总体 O(E log E)。边少时 Kruskal 很划算，所以稀疏图 → Kruskal，稠密图 → Prim。

⚠️ 常见错误

1. 忘路径压缩：find 不压缩，并查集会退化成链表，性能崩坏。
2. union 前不判同根：同根还合并，会破坏并查集不变量，导致成环边也被算进去。
3. 选满 n-1 条边后不 break：不影响正确性但浪费；更重要的是必须检查 cnt 是否达到 n-1，否则图不连通。
4. 排序 key 写错：edges.sort() 默认按 (u, v, w) 整体排，语义易错；明确 key=lambda e: e[2] 最稳。

---

8.9 Prim vs Kruskal

维度	Prim	Kruskal
思路	从一个点向外「长」树	全局边排序，从小到大选
数据结构	优先队列（堆）	并查集
依据性质	切割性质	回路性质
时间复杂度	O((V+E)log V)	O(E log E)
适合	稠密图	稀疏图
边数影响	主要看 V	主要看 E

一句话：Prim 生长、Kruskal 选边。两者对同一图的总权值一致。

---

🧠 记忆口诀

• 最短路径三选一：非负单源 → Dijkstra；负权单源 → Bellman-Ford；全点对 → Floyd。
• Dijkstra 一句话：当前最小的未确定点，就是最终答案（贪心，依赖非负）。
• Bellman-Ford：边整体松弛 n-1 轮，再松一轮能松就有负环。
• Floyd：k 在最外层，i→k→j 逐点插队。
• MST 两兄弟：Prim 长树（堆），Kruskal 选边（并查集）；稀疏 Kruskal、稠密 Prim。

⭐ 考点清单

1. 单源/多源、非负/负权的分类与算法选择
2. Dijkstra 堆实现、过期记录 continue、为什么负权失效
3. Bellman-Ford 的 n-1 轮松弛与负环检测
4. Floyd 三重循环顺序、k 在最外层、负环检测（对角为负）
5. 切割性质与回路性质的含义
6. Prim 堆实现、与 Dijkstra 的异同
7. Kruskal 排序 + 并查集、并查集 find/union/路径压缩
8. 三兄弟与两兄弟的时间复杂度、适用场景
9. MST 不唯一但总权值唯一；n-1 条边；图不连通返回 None

📌 中英术语表

中文	English	说明
最短路径	shortest path	两点之间权值和最小的路径
单源最短路径	single-source shortest path	一个起点到所有点
多源最短路径	all-pairs shortest path	任意两点之间
松弛	relaxation	尝试用更短路径更新某点距离
优先队列	priority queue	堆，每次取最小 / 最大
Dijkstra 算法	Dijkstra's algorithm	非负权单源最短路，贪心
Bellman-Ford 算法	Bellman-Ford algorithm	可负权单源最短路
Floyd-Warshall 算法	Floyd-Warshall algorithm	多源最短路，动态规划
负权环	negative cycle	总权为负的环，最短路无意义
生成树	spanning tree	n 点 n-1 条边连通无环
最小生成树	minimum spanning tree (MST)	总权最小的生成树
切割性质	cut property	跨切割的最小边必在某个 MST
回路性质	cycle property	环上最大边必不在 MST
Prim 算法	Prim's algorithm	贪心生长，稠密图适用
Kruskal 算法	Kruskal's algorithm	边排序选边，稀疏图适用
并查集	union-find / disjoint set	快速判断两点连通并合并
路径压缩	path compression	找根时把沿途点直接连到根
稠密图 / 稀疏图	dense / sparse graph	边多 / 边少