最短路与最小生成树
第十八章：最短路与最小生成树
图的遍历（BFS/DFS）告诉我们"哪些节点可达"，但在现实世界中，我们更关心的是代价：从 A 到 B 的最快路线是什么？连接所有城市的最便宜光纤网络怎么布？这两个问题分别对应图论中最经典的两大优化问题——最短路径（Shortest Path） 和最小生成树（Minimum Spanning Tree, MST）。
这两个问题看起来类似（都是在带权图上找"最优"结构），但本质完全不同：最短路是源到目标的路径优化，MST 是全局连通的边集优化。它们的算法设计思路也截然不同——最短路依赖松弛（relaxation） 操作逐步逼近最优解，MST 依赖贪心（greedy） 策略逐步构建最优解。
这一章我们要彻底掌握五个核心算法：Dijkstra（单源最短路，非负权）、Bellman-Ford（单源最短路，允许负权）、Floyd-Warshall（全源最短路）、Prim（MST，从点出发）、Kruskal（MST，从边出发）。每个算法我们都会回答：它解决什么问题？它为什么正确？它的时间复杂度是多少？什么场景下应该选择它？
Level 1 · 你需要知道的
18.1 问题定义
单源最短路径（Single-Source Shortest Path, SSSP）：给定一个带权有向图 G=(V, E) 和源节点 s，求 s 到所有其他节点的最短路径距离。
全源最短路径（All-Pairs Shortest Path, APSP）：求所有节点对之间的最短路径距离。
最小生成树（Minimum Spanning Tree, MST）：给定一个带权无向连通图 G=(V, E)，找到一棵包含所有节点的树，使得边权之和最小。
带权有向图示例（SSSP）：
A --2--> B --3--> D
| ^ ^
4 1 2
| | |
v | |
C --1--> B' E ---+
\ ^
5 |
\ |
+--> E ---+
带权无向连通图示例（MST）：
A ---4--- B
| \ | \
1 3 6 5
| \ | \
C ---2--- D ---7--- E
关键区别：
- 最短路：可以有环，可以有负权边（Bellman-Ford），目标是路径。
- MST：只在无向连通图上定义，不能有负权环（无向图无此问题），目标是边的集合（树）。
18.2 Dijkstra 算法
适用条件：边权非负的图（无向/有向均可）。
核心思想：维护一个"已确定最短距离"的节点集合 S，每次从未确定的节点中选择距离最小的节点 u，将其加入 S，然后用 u 的出边去松弛（relax） 其邻居的距离。
松弛操作：如果 dist[u] + w(u,v) < dist[v]，则更新 dist[v] = dist[u] + w(u,v)。
import heapq
from typing import List, Tuple, Dict
def dijkstra(graph: Dict[int, List[Tuple[int, int]]], source: int, n: int) -> List[float]:
"""
Dijkstra 算法 - 优先队列实现
参数:
graph: 邻接表，graph[u] = [(v, weight), ...]
source: 源节点
n: 节点数量 (0 到 n-1)
返回:
dist: dist[i] 表示 source 到节点 i 的最短距离
"""
dist = [float('inf')] * n
dist[source] = 0
# 优先队列: (距离, 节点)
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
# 关键优化：如果取出的距离大于已知最短距离，跳过
if d > dist[u]:
continue
# 松弛所有邻居
for v, weight in graph[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
使用示例：
# 构建图
graph = {
0: [(1, 2), (2, 4)], # 0->1 权重2, 0->2 权重4
1: [(2, 1), (3, 7)], # 1->2 权重1, 1->3 权重7
2: [(3, 3)], # 2->3 权重3
3: []
}
dist = dijkstra(graph, 0, 4)
print(dist) # [0, 2, 3, 6]
# 解释: 0->0=0, 0->1=2, 0->1->2=3, 0->1->2->3=6
时间复杂度：O((V + E) log V)。每个节点最多入队 V 次（实际远少于此），每次入队/出队 O(log V)。
常见错误：
# 错误1：图中有负权边时使用 Dijkstra
graph = {0: [(1, -3), (2, 2)], 1: [(2, 1)], 2: []}
# Dijkstra 会得到 dist[2] = 2（直接走 0->2）
# 但实际最短路是 0->1->2 = -3+1 = -2
# 因为 Dijkstra 一旦确定节点就不再更新！
# 错误2：忘记跳过过期的队列条目
def dijkstra_wrong(graph, source, n):
dist = [float('inf')] * n
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
# 没有 if d > dist[u]: continue
# 导致重复处理已确定的节点，虽然结果正确但时间大增
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
18.3 Bellman-Ford 算法
适用条件：允许负权边的图。可以检测负环（从源可达的负权环）。
核心思想：对所有边重复执行松弛操作 V-1 次。因为最短路径最多包含 V-1 条边（无环情况下），所以 V-1 轮松弛一定能找到所有最短路径。
def bellman_ford(edges: List[Tuple[int, int, int]], source: int, n: int) -> Tuple[List[float], bool]:
"""
Bellman-Ford 算法
参数:
edges: 边列表 [(u, v, weight), ...]
source: 源节点
n: 节点数量
返回:
(dist, has_negative_cycle): 距离数组和是否存在负环
"""
dist = [float('inf')] * n
dist[source] = 0
# V-1 轮松弛
for i in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
# 提前终止优化：如果某轮没有任何更新，已收敛
if not updated:
break
# 第 V 轮检测负环
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return dist, True # 存在负环
return dist, False
为什么 V-1 轮就够了？ 如果最短路径经过 k 条边，那么第 k 轮松弛时它一定被正确计算出来。一条简单路径最多经过 V-1 条边（经过所有 V 个节点），所以 V-1 轮足够。
时间复杂度：O(VE)。V-1 轮，每轮遍历所有 E 条边。
使用示例：
edges = [
(0, 1, 4),
(0, 2, 5),
(1, 2, -3), # 负权边
(2, 3, 4),
(3, 1, -2), # 注意：1->2->3->1 构成环，权重 = -3+4-2 = -1 < 0，负环！
]
dist, has_neg_cycle = bellman_ford(edges, 0, 4)
if has_neg_cycle:
print("图中存在负环，最短路径无定义")
else:
print(dist)
18.4 Floyd-Warshall 算法
适用条件：全源最短路径。允许负权边，但不能有负环。
核心思想：动态规划。定义 dp[k][i][j] = 从 i 到 j 只经过编号 ≤ k 的中间节点的最短路径。转移方程：
dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
要么不经过节点 k（继承 dp[k-1][i][j]），要么经过节点 k（i→k 和 k→j 的路径拼接）。
def floyd_warshall(n: int, edges: List[Tuple[int, int, int]]) -> List[List[float]]:
"""
Floyd-Warshall 全源最短路径
参数:
n: 节点数量
edges: 边列表 [(u, v, weight), ...]
返回:
dist: dist[i][j] 表示 i 到 j 的最短距离
"""
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
# 初始化
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w) # 处理重边
# DP: 逐步加入中间节点
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
时间复杂度：O(V³)。空间优化后为 O(V²)（原地更新 dist 矩阵）。
适用场景：
- 节点数较少（V ≤ 几百）但需要所有点对最短路径
- 图是稠密的（邻接矩阵表示更方便）
- 需要检测负环（如果
dist[i][i] < 0，则存在经过 i 的负环）
18.5 最小生成树：Prim 算法
适用条件：带权无向连通图。
核心思想：从任意起点开始，每次选择连接"已在树中的节点"和"不在树中的节点"的最小权边，将其加入 MST。这是一种贪心策略。
def prim(graph: Dict[int, List[Tuple[int, int]]], n: int) -> Tuple[int, List[Tuple[int, int, int]]]:
"""
Prim 算法 - 优先队列实现
参数:
graph: 无向图邻接表，graph[u] = [(v, weight), ...]
n: 节点数量
返回:
(total_weight, mst_edges): MST 总权重和边列表
"""
visited = [False] * n
mst_edges = []
total_weight = 0
# (权重, 目标节点, 来源节点)
pq = [(0, 0, -1)] # 从节点 0 开始
while pq and len(mst_edges) < n - 1:
weight, u, parent = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
total_weight += weight
if parent != -1:
mst_edges.append((parent, u, weight))
for v, w in graph[u]:
if not visited[v]:
heapq.heappush(pq, (w, v, u))
return total_weight, mst_edges
时间复杂度：O((V + E) log V)（用二叉堆），O(E + V log V)（用 Fibonacci 堆）。
18.6 最小生成树：Kruskal 算法
核心思想：将所有边按权重排序，从小到大依次考虑每条边。如果加入这条边不会形成环（用并查集判断），就加入 MST。
class UnionFind:
"""并查集 - 路径压缩 + 按秩合并"""
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # 已连通，加入会形成环
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> Tuple[int, List[Tuple[int, int, int]]]:
"""
Kruskal 算法
参数:
n: 节点数量
edges: 边列表 [(u, v, weight), ...]
返回:
(total_weight, mst_edges): MST 总权重和边列表
"""
# 按权重排序
edges.sort(key=lambda e: e[2])
uf = UnionFind(n)
mst_edges = []
total_weight = 0
for u, v, w in edges:
if uf.union(u, v):
mst_edges.append((u, v, w))
total_weight += w
if len(mst_edges) == n - 1:
break
return total_weight, mst_edges
时间复杂度：O(E log E)（排序主导），即 O(E log V)（因为 E ≤ V²，所以 log E = O(log V)）。
Prim vs Kruskal 快速选择：
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 稠密图（E 接近 V²） | Prim | 不需要排序所有边 |
| 稀疏图（E 接近 V） | Kruskal | 排序代价低，并查集简单 |
| 已有并查集实现 | Kruskal | 代码更简洁 |
| 需要在线添加节点 | Prim | 方便从当前树扩展 |
| 面试默写 | Kruskal | 实现更短，不容易出错 |
18.7 完整示例：从零构建
"""
综合示例：一个城市道路网络
"""
def demo():
# 城市网络：6 个城市，双向道路
# 边: (城市A, 城市B, 距离)
roads = [
(0, 1, 7), (0, 2, 9), (0, 5, 14),
(1, 2, 10), (1, 3, 15),
(2, 3, 11), (2, 5, 2),
(3, 4, 6),
(4, 5, 9)
]
n = 6
# 1. 单源最短路 (Dijkstra)
graph = {i: [] for i in range(n)}
for u, v, w in roads:
graph[u].append((v, w))
graph[v].append((u, w)) # 无向图
dist = dijkstra(graph, 0, n)
print("从城市0出发的最短距离:", dist)
# [0, 7, 9, 20, 20, 11]
# 2. 全源最短路 (Floyd-Warshall)
# 无向图需要添加双向边
directed_edges = []
for u, v, w in roads:
directed_edges.append((u, v, w))
directed_edges.append((v, u, w))
all_dist = floyd_warshall(n, directed_edges)
print("城市2到城市4的最短距离:", all_dist[2][4])
# 3. 最小生成树 (Kruskal)
total, mst = kruskal(n, roads[:]) # 传入副本因为会排序
print(f"连接所有城市的最小道路总长: {total}")
print("选择的道路:", mst)
demo()
Level 2 · 它是怎么运行的
18.8 Dijkstra 的正确性证明
定理：对于边权非负的图，Dijkstra 算法正确计算所有从源可达节点的最短距离。
证明（归纳法）：
设 S 是已确定最短距离的节点集合。我们证明：每次将节点 u 加入 S 时，dist[u] 确实是 s 到 u 的最短距离。
基础情况：源节点 s 加入 S 时，dist[s] = 0，正确。
归纳步骤：假设 S 中所有节点的距离都已正确计算。设 u 是下一个被选中的节点（dist 值最小的未确定节点）。
反证法：假设存在一条更短的路径 P: s → ... → x → y → ... → u，其中 x ∈ S，y ∉ S。
- 因为 y 是 P 上第一个不在 S 中的节点，s → ... → x → y 这段路径的长度 ≤ P 的总长度。
- 又因为边权非负，s → ... → x → y 的长度 ≤ s → ... → x → y → ... → u 的长度。
- 由归纳假设，dist[x] 正确，所以在处理 x 时已经松弛了 y，即 dist[y] ≤ dist[x] + w(x,y) = s→...→x→y 的长度。
- 但 u 是 dist 值最小的未确定节点，所以 dist[u] ≤ dist[y]。
- 综合：dist[u] ≤ dist[y] ≤ P 的长度 < dist[u]，矛盾！
因此 dist[u] 就是最短距离。
为什么负权边会破坏正确性？ 如果存在边权为负的边 (y, ..., u) 上有负权边，那么 "s → ... → x → y → ... → u" 的长度可能小于 "s → ... → x → y"（后面的边减小了总距离），此时 dist[y] ≤ dist[u] 不再成立，归纳假设被破坏。
18.9 SPFA：Bellman-Ford 的队列优化
SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的实用优化。核心观察：如果节点 u 的 dist 值在某轮没有被更新，那么 u 的出边在下一轮不可能产生新的松弛。所以我们只对"刚被更新过的节点"做松弛，用队列维护这些节点。
from collections import deque
def spfa(graph: Dict[int, List[Tuple[int, int]]], source: int, n: int) -> Tuple[List[float], bool]:
"""
SPFA (Shortest Path Faster Algorithm)
Bellman-Ford 的队列优化版本
返回:
(dist, has_negative_cycle)
"""
dist = [float('inf')] * n
dist[source] = 0
in_queue = [False] * n
count = [0] * n # count[v] = v 入队次数，超过 n-1 次说明有负环
queue = deque([source])
in_queue[source] = True
while queue:
u = queue.popleft()
in_queue[u] = False
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
count[v] += 1
if count[v] >= n:
return dist, True # 负环
return dist, False
复杂度分析：
- 最坏情况：O(VE)，和 Bellman-Ford 相同（精心构造的负权图可以使 SPFA 退化）。
- 平均情况：O(kE)，其中 k 是一个很小的常数（经验上约为 2）。
- 注意：不要在竞赛中对有负权的图盲目信任 SPFA 的"平均复杂度"，出题人可以卡 SPFA。
SLF（Shortest Label First）优化：将新入队的节点与队首比较，如果 dist 更小就插入队首而非队尾。
# SLF 优化
if not in_queue[v]:
if queue and dist[v] < dist[queue[0]]:
queue.appendleft(v) # 插入队首
else:
queue.append(v) # 插入队尾
in_queue[v] = True
18.10 负环检测的深入分析
方法一：Bellman-Ford 第 V 轮检测（前面已展示）
方法二：SPFA 入队次数检测 —— 如果某节点入队超过 V-1 次，说明存在负环。
方法三：DFS + 标记（检测图中任意位置的负环）
def detect_negative_cycle_dfs(graph: Dict[int, List[Tuple[int, int]]], n: int) -> bool:
"""
检测图中是否存在负环（从任意位置出发）
思路：添加一个虚拟源节点连接所有节点，权重为0
"""
# 添加虚拟源节点 n，连接到所有节点
edges = []
for u in range(n):
edges.append((n, u, 0))
for v, w in graph[u]:
edges.append((u, v, w))
dist, has_neg_cycle = bellman_ford(edges, n, n + 1)
return has_neg_cycle
实际应用：套汇检测。外汇市场中，汇率可以建模为图的边权（取对数后变为加法）。如果存在负环，意味着存在套利机会：按环路兑换一圈后能获得更多的起始货币。
import math
def detect_arbitrage(currencies: List[str], rates: List[List[float]]) -> bool:
"""
检测外汇套利机会
rates[i][j] = 1单位货币i 能兑换多少货币j
取 -log 后，乘法变加法，>1 变 <0
套利等价于负环
"""
n = len(currencies)
edges = []
for i in range(n):
for j in range(n):
if i != j and rates[i][j] > 0:
# -log(rate) 将乘法转为加法，rate>1 的边变成负权
edges.append((i, j, -math.log(rates[i][j])))
# 用 Bellman-Ford 检测负环
dist = [0.0] * n # 从所有节点同时开始（等价于虚拟源）
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # 存在套利机会
return False
18.11 Prim vs Kruskal：深入对比
理论基础——切割性质（Cut Property）：
对于图的任意切割（将顶点分成两个非空集合 S 和 V\S），横跨切割的最小权边一定属于某个 MST。
- Prim 利用切割性质：S = 已加入 MST 的节点集，每次选 S 和 V\S 之间的最小边。
- Kruskal 利用切割性质：每次选全局最小的不形成环的边，等价于每次选择"当前任意一个切割的最小横跨边"。
为什么两者都正确？ 因为都在利用切割性质。每一步选择的边都必须属于 MST。这是贪心正确性的数学保证。
实现复杂度对比：
| 操作 | Prim (二叉堆) | Prim (Fibonacci堆) | Kruskal |
|---|---|---|---|
| 总时间 | O((V+E) log V) | O(E + V log V) | O(E log E) |
| 适用场景 | 稠密图 | 理论最优 | 稀疏图 |
| 代码复杂度 | 中 | 高 | 低 |
| 空间 | O(V) | O(V) | O(V+E) |
关键洞察：对于稠密图（E ≈ V²），Prim 为 O(V² log V) 而 Kruskal 为 O(V² log V)，差别不大。但如果用邻接矩阵实现 Prim（不用堆，直接遍历找最小），Prim 是 O(V²)，此时 Prim 明显优于 Kruskal。
def prim_dense(adj_matrix: List[List[float]], n: int) -> int:
"""
Prim 的邻接矩阵实现 - 适用于稠密图
时间 O(V²)，不使用堆
"""
INF = float('inf')
in_mst = [False] * n
min_edge = [INF] * n # min_edge[v] = v 到 MST 集合的最小边权
min_edge[0] = 0
total = 0
for _ in range(n):
# 找到不在 MST 中的最小 min_edge 节点
u = -1
for v in range(n):
if not in_mst[v] and (u == -1 or min_edge[v] < min_edge[u]):
u = v
in_mst[u] = True
total += min_edge[u]
# 更新邻居的 min_edge
for v in range(n):
if not in_mst[v] and adj_matrix[u][v] < min_edge[v]:
min_edge[v] = adj_matrix[u][v]
return total
18.12 路径还原
算法不仅要计算最短距离，还经常需要输出具体路径。方法是记录每个节点的前驱（predecessor）。
def dijkstra_with_path(graph: Dict[int, List[Tuple[int, int]]], source: int, n: int):
"""Dijkstra + 路径还原"""
dist = [float('inf')] * n
dist[source] = 0
prev = [-1] * n # 前驱数组
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, prev
def reconstruct_path(prev: List[int], target: int) -> List[int]:
"""从前驱数组还原路径"""
path = []
node = target
while node != -1:
path.append(node)
node = prev[node]
path.reverse()
return path
# 使用
dist, prev = dijkstra_with_path(graph, 0, 6)
path = reconstruct_path(prev, 5)
print(f"0 到 5 的最短路径: {' -> '.join(map(str, path))}")
print(f"距离: {dist[5]}")
18.13 算法选择决策树
面对最短路问题时，按以下顺序决策：
1. 是否需要所有点对的最短路？
├─ 是 → V ≤ 几百？
│ ├─ 是 → Floyd-Warshall O(V³)
│ └─ 否 → 运行 V 次 Dijkstra O(VE log V) 或 Johnson 算法
└─ 否 → 单源最短路
├─ 有负权边？
│ ├─ 是 → Bellman-Ford O(VE) 或 SPFA
│ └─ 否 → Dijkstra O((V+E) log V)
└─ 边权全为 1？
└─ BFS O(V+E) （最简单最快）
Level 3 · 规范怎么定义的
18.14 Dijkstra 1959 年论文
论文：Edsger W. Dijkstra, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik, 1959.
这篇仅三页的短文解决了两个问题：(1) 最短路径，(2) 最小生成树。Dijkstra 在文中简洁地描述了算法，甚至没有给出正式证明——他认为正确性"显而易见"。
历史背景：Dijkstra 当时在阿姆斯特丹数学中心工作，这个算法的灵感来自于实际问题——为 ARMAC 计算机的演示设计一个程序，计算荷兰64个城市之间的最短铁路路线。
原文描述的算法（用现代术语重述）：
- 将所有节点标记为"未访问"，距离设为 ∞，源节点距离设为 0。
- 选择距离最小的未访问节点 u。
- 对 u 的所有邻居 v 执行松弛。
- 将 u 标记为"已访问"。
- 重复直到所有节点已访问。
Dijkstra 原文中没有使用优先队列——他用的是线性扫描找最小值，时间复杂度为 O(V²)。优先队列优化是后来的工作（Johnson 1977，Fredman & Tarjan 1987 的 Fibonacci 堆实现）。
趣事：Dijkstra 后来在一次采访中说："这个算法花了我大约20分钟。有一天早上我在阿姆斯特丹和我年轻的未婚妻一起逛街，累了，我们就在咖啡厅的露台坐下喝咖啡，然后我就想到了这个算法。"
18.15 Bellman 1958 / Ford 1956
Richard Bellman 在 1958 年的论文 "On a Routing Problem" 中描述了这个算法，作为他发展动态规划理论的一部分。
Lester R. Ford Jr. 在 1956 年的 RAND Corporation 备忘录中独立描述了同样的算法。
实际上，Alfonso Shimbel 在 1955 年就描述了类似算法。所以这个算法有时也被称为 Bellman-Ford-Moore 算法（Edward F. Moore 在 1959 年也独立发现了它）。
Bellman 的动态规划视角：定义 d_k(v) = 从 s 到 v 的最多经过 k 条边的最短路径。递推关系：
d_k(v) = min(d_{k-1}(v), min_{(u,v)∈E} (d_{k-1}(u) + w(u,v)))
这正是 Bellman-Ford 算法的本质——一个动态规划的"按阶段松弛"过程。
最优性原理（Bellman, 1957）："最优策略的任何子策略也是最优的。" 应用到最短路：如果 s→...→u→v 是 s 到 v 的最短路径，那么 s→...→u 必然是 s 到 u 的最短路径。这是所有最短路算法正确性的基础。
18.16 Floyd 1962
论文：Robert W. Floyd, "Algorithm 97: Shortest Path", Communications of the ACM, 1962.
Floyd 的论文极其简短（不到一页），只给出了算法的三重循环实现。但其背后的思想——逐步放松"允许经过哪些中间节点"——是动态规划在图论中的经典应用。
与 Warshall 的关系：Stephen Warshall 在 1962 年发表的 "A Theorem on Boolean Matrices" 解决了传递闭包问题（判断节点间是否可达），使用了完全相同的三重循环结构。Floyd 将 Warshall 的布尔矩阵扩展为带权矩阵，将"可达性"推广为"最短距离"。
与 Kleene 算法的关系：更深层地看，Floyd-Warshall 本质上是 Kleene 在正则表达式/有限自动机理论中的算法在半环（semiring）上的推广。加法半环 (min, +) 上的 Kleene 算法就是 Floyd-Warshall；布尔半环 (∨, ∧) 上的就是 Warshall 的传递闭包。
18.17 Kruskal 1956 与 Prim 1957
Joseph B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", Proceedings of the American Mathematical Society, 1956.
Kruskal 的论文不仅提出了 MST 算法，还讨论了与旅行商问题的关系。他证明了贪心策略的正确性：按边权从小到大选择不形成环的边。
Robert C. Prim, "Shortest Connection Networks And Some Generalizations", Bell System Technical Journal, 1957.
Prim 在 Bell 实验室工作时独立发现了这个算法。有趣的是，捷克数学家 Vojtěch Jarník 早在 1930 年就在论文 "O jistém problému minimálním" 中描述了本质相同的算法。因此这个算法有时也被称为 Jarník-Prim 算法或 DJP 算法（Dijkstra-Jarník-Prim，因为 Dijkstra 1959 年的论文也独立描述了它）。
切割性质的形式化证明（MST 正确性的基石）：
定理（Cut Property）：设 (S, V\S) 是图 G 的任意切割，e 是横跨该切割的唯一最小权边。则 e 属于 G 的每一个 MST。
证明：反证法。设 T 是一个 MST 且 e = (u,v) ∉ T。在 T 中，u 和 v 之间有一条路径 P（因为 T 是连通的）。P 必须横跨切割（因为 u ∈ S, v ∈ V\S），所以 P 上有一条横跨边 e' ≠ e。由于 e 是横跨切割的唯一最小权边，w(e) < w(e')。将 e' 从 T 中删除并加入 e，得到新的生成树 T'。w(T') = w(T) - w(e') + w(e) < w(T)，与 T 是 MST 矛盾。■
推广：如果最小横跨边不唯一（有并列），则至少存在一个包含该边的 MST。
18.18 复杂度下界与最优算法
最短路径的复杂度下界：
- 单源最短路的比较模型下界是 Ω(V + E)（必须至少看一遍所有边）。
- Dijkstra + Fibonacci 堆达到 O(E + V log V)，对于稠密图（E = Θ(V²)）是最优的。
- 对于稀疏图，是否存在 O(V + E) 的确定性算法至今是开放问题。
MST 的复杂度下界：
- 比较模型下界 Ω(E)（必须看所有边）。
- Chazelle (2000) 给出了 O(E α(V)) 的算法（α 是逆 Ackermann 函数，实际上约等于常数）。
- Pettie & Ramachandran (2002) 给出了最优确定性算法，但其复杂度不能用标准函数表达。
- 在随机化模型下，Karger, Klein & Tarjan (1995) 给出了期望 O(V + E) 的线性时间算法。
Level 4 · 边界与陷阱
18.19 LeetCode 743：网络延迟时间
题目：有 n 个网络节点，给定有向边 times[i] = [u, v, w]（从 u 到 v 传输时间为 w），从节点 k 发送信号，返回所有节点收到信号的最短时间。如果有节点不可达，返回 -1。
分析：典型的单源最短路问题。所有边权为正（传输时间），直接用 Dijkstra。
def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
"""
LeetCode 743: Network Delay Time
直接的 Dijkstra 应用
"""
# 建图（注意节点编号从 1 开始）
graph = {i: [] for i in range(1, n + 1)}
for u, v, w in times:
graph[u].append((v, w))
# Dijkstra
dist = {i: float('inf') for i in range(1, n + 1)}
dist[k] = 0
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
result = max(dist.values())
return result if result < float('inf') else -1
# 测试
times = [[2,1,1],[2,3,1],[3,4,1]]
print(networkDelayTime(times, 4, 2)) # 2
# 从节点2出发: 2->1(1), 2->3(1), 2->3->4(2)
# 所有节点最远距离 = 2
复杂度：O((V + E) log V)，其中 V = n, E = len(times)。
面试追问：
- Q: "如果边权可以为负呢？" → 用 Bellman-Ford。
- Q: "如果要返回具体的传播路径呢？" → 记录 prev 数组。
- Q: "如果图很大（百万节点），有什么优化？" → 如果只需要到某个特定目标，可以用 A* 或双向 Dijkstra。
18.20 LeetCode 1631：最小体力消耗路径
题目：给定一个 rows×columns 的高度矩阵 heights，从左上角 (0,0) 到右下角 (rows-1, columns-1)，路径的"体力消耗"定义为路径上相邻格子高度差的绝对值的最大值。求最小体力消耗。
分析：这不是传统的"路径距离和最小"问题，而是"路径上最大边权最小"（minimax path）。但核心思路仍然可以用 Dijkstra 的变体解决！
关键洞察：将 dist[v] 的含义从"路径权重之和"改为"路径上最大边权"，松弛操作从 dist[u] + w 改为 max(dist[u], w)。Dijkstra 的贪心策略仍然成立——因为从优先队列中取出的最小 dist 值节点，不可能通过其他路径获得更小的"最大边权"。
def minimumEffortPath(heights: List[List[int]]) -> int:
"""
LeetCode 1631: Path With Minimum Effort
变体 Dijkstra：dist 定义为路径上最大边权
"""
rows, cols = len(heights), len(heights[0])
# dist[r][c] = 从 (0,0) 到 (r,c) 的最小体力消耗
dist = [[float('inf')] * cols for _ in range(rows)]
dist[0][0] = 0
# (体力消耗, 行, 列)
pq = [(0, 0, 0)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while pq:
effort, r, c = heapq.heappop(pq)
if r == rows - 1 and c == cols - 1:
return effort
if effort > dist[r][c]:
continue
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
# 边权 = 高度差的绝对值
edge_weight = abs(heights[nr][nc] - heights[r][c])
# 新的 dist = max(当前路径最大边权, 这条新边)
new_effort = max(effort, edge_weight)
if new_effort < dist[nr][nc]:
dist[nr][nc] = new_effort
heapq.heappush(pq, (new_effort, nr, nc))
return 0 # 只有一个格子
# 测试
heights = [[1,2,2],[3,8,2],[5,3,5]]
print(minimumEffortPath(heights)) # 2
# 路径 (0,0)->(0,1)->(0,2)->(1,2)->(2,2)，最大差值 = |5-3| 或 |2-2|...
# 实际最优路径最大差值为 2
替代解法——二分答案 + BFS：
def minimumEffortPath_binary_search(heights: List[List[int]]) -> int:
"""二分答案：猜测最大体力消耗 mid，用 BFS 验证是否存在可行路径"""
rows, cols = len(heights), len(heights[0])
def can_reach(max_effort: int) -> bool:
"""判断是否存在一条路径，使得最大边权 ≤ max_effort"""
visited = [[False] * cols for _ in range(rows)]
queue = deque([(0, 0)])
visited[0][0] = True
while queue:
r, c = queue.popleft()
if r == rows - 1 and c == cols - 1:
return True
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
if abs(heights[nr][nc] - heights[r][c]) <= max_effort:
visited[nr][nc] = True
queue.append((nr, nc))
return False
lo, hi = 0, 10**6
while lo < hi:
mid = (lo + hi) // 2
if can_reach(mid):
hi = mid
else:
lo = mid + 1
return lo
替代解法——并查集 + 边排序（本质上是 Kruskal 思路）：
def minimumEffortPath_kruskal(heights: List[List[int]]) -> int:
"""
Kruskal 思路：将所有边按权重排序，依次加入直到起点和终点连通
"""
rows, cols = len(heights), len(heights[0])
# 生成所有边
edges = []
for r in range(rows):
for c in range(cols):
idx = r * cols + c
if c + 1 < cols:
w = abs(heights[r][c+1] - heights[r][c])
edges.append((w, idx, idx + 1))
if r + 1 < rows:
w = abs(heights[r+1][c] - heights[r][c])
edges.append((w, idx, idx + cols))
edges.sort()
uf = UnionFind(rows * cols)
source = 0
target = rows * cols - 1
for w, u, v in edges:
uf.union(u, v)
if uf.find(source) == uf.find(target):
return w
return 0
这道题完美展示了三种不同的算法范式如何解决同一个问题：Dijkstra 变体、二分答案 + BFS、Kruskal 变体。面试中能给出多种解法并分析优劣是加分项。
18.21 LeetCode 1584：连接所有点的最小费用
题目：给定 n 个点 points[i] = [xi, yi]，两点间连接费用为曼哈顿距离 |xi-xj| + |yi-yj|。返回使所有点连通的最小费用。
分析：经典的最小生成树问题。完全图（任意两点可连边），n 个点有 n(n-1)/2 条边。
def minCostConnectPoints(points: List[List[int]]) -> int:
"""
LeetCode 1584: Min Cost to Connect All Points
方法1: Kruskal（所有边排序）
"""
n = len(points)
# 生成所有边
edges = []
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((dist, i, j))
edges.sort()
uf = UnionFind(n)
total = 0
count = 0
for w, u, v in edges:
if uf.union(u, v):
total += w
count += 1
if count == n - 1:
break
return total
def minCostConnectPoints_prim(points: List[List[int]]) -> int:
"""
方法2: Prim（优先队列），对完全图更高效
Kruskal 需要 O(n²) 条边全部排序: O(n² log n)
Prim 每次只需要处理当前节点的边: O(n² log n) 但常数更小
实际上对完全图，不用堆的 Prim O(n²) 最优
"""
n = len(points)
# 不用堆的 Prim，O(n²)
in_mst = [False] * n
min_dist = [float('inf')] * n # 到 MST 集合的最小距离
min_dist[0] = 0
total = 0
for _ in range(n):
# 找最小 min_dist 的非 MST 节点
u = -1
for v in range(n):
if not in_mst[v] and (u == -1 or min_dist[v] < min_dist[u]):
u = v
in_mst[u] = True
total += min_dist[u]
# 更新其他节点到 MST 的距离
for v in range(n):
if not in_mst[v]:
d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
min_dist[v] = min(min_dist[v], d)
return total
# 测试
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
print(minCostConnectPoints(points)) # 20
print(minCostConnectPoints_prim(points)) # 20
性能对比：
- Kruskal: O(n² log n) 时间，O(n²) 空间（存所有边）
- Prim (无堆): O(n²) 时间，O(n) 空间
- 对于本题 n ≤ 1000，两者都能通过。但 Prim 无堆版本在完全图上是最优选择。
18.22 常见陷阱与面试技巧总结
陷阱 1：Dijkstra 遇到负权边
# 经典反例
# 0 -> 1 (权重 1)
# 0 -> 2 (权重 5)
# 1 -> 2 (权重 -10)
# Dijkstra: 先确定 dist[1]=1, 然后 dist[2]=5 已确定
# 实际最短: 0->1->2 = 1+(-10) = -9
面试中如果题目保证边权非负，用 Dijkstra；否则必须用 Bellman-Ford。
陷阱 2：Floyd-Warshall 的循环顺序
# 正确：k 在最外层
for k in range(n):
for i in range(n):
for j in range(n):
...
# 错误：k 不在最外层会导致结果错误
# 因为 dp[k] 依赖 dp[k-1]，k 必须是外层循环
陷阱 3：MST 不等于最短路径树
A --1-- B --1-- C
| |
3 3
| |
D ------1------ E
MST 包含 A-B, B-C, D-E, 和 A-D 或 C-E (总权重 6)
但从 A 到 E 的最短路径是 A-B-C-E (权重 5)，不走 MST 的边
陷阱 4：图不连通时 MST 不存在
def kruskal_safe(n, edges):
total, mst = kruskal(n, edges)
if len(mst) < n - 1:
return -1 # 图不连通，MST 不存在
return total
面试模板总结：
| 问题类型 | 算法 | 关键代码 |
|---|---|---|
| 单源最短路（正权） | Dijkstra | heapq + dist 数组 |
| 单源最短路（有负权） | Bellman-Ford/SPFA | V-1 轮松弛 |
| 全源最短路 | Floyd-Warshall | 三重循环，k 最外层 |
| 最小生成树 | Kruskal | 排序 + 并查集 |
| 最小生成树（稠密图） | Prim | min_dist 数组 |
| minimax 路径 | Dijkstra 变体 | max 代替 + |
| 判定连通性 | 并查集/BFS | union + find |
时间复杂度速查：
| 算法 | 时间 | 空间 | 适用条件 |
|---|---|---|---|
| Dijkstra (堆) | O((V+E) log V) | O(V+E) | 非负权 |
| Bellman-Ford | O(VE) | O(V) | 任意权（可检测负环） |
| SPFA | 平均 O(kE) 最坏 O(VE) | O(V+E) | 任意权 |
| Floyd-Warshall | O(V³) | O(V²) | 全源，V 小 |
| Prim (堆) | O((V+E) log V) | O(V+E) | 无向连通图 |
| Prim (无堆) | O(V²) | O(V) | 稠密图 |
| Kruskal | O(E log E) | O(V+E) | 无向连通图 |