最小生成树和最短路径 · 融合风（象牙 + Obsidian 入口）

速查

MST 连接所有顶点、总权最小（Prim $O(n^2)$ / Kruskal $O(e\log e)$）；最短路径 Dijkstra 单源 $O(n^2)$（无负权边）、Floyd 多源 $O(n^3)$（无负权回路）。

速查 ▾

项目	值
主题	最小生成树和最短路径
核心概念	MST：连通带权无向图中总权值最小的生成树，恰 $n-1$ 条边
时间复杂度	$O(e\log e)$、$O(n^2)$、$O(n^3)$
难度	⭐⭐⭐
重要性	⭐⭐

核心概念 ▾

一、最小生成树（MST）

连通带权无向图中，总权值最小的生成树；$n$ 个顶点的 MST 恰好有 $n-1$ 条边。

Prim 算法（加点法）：每次选连接已选集与未选集中权值最小的边，时间 $O(n^2)$，适合稠密图
Kruskal 算法（加边法）：边排序后依次选不构成回路的最小边，时间 $O(e\log e)$，适合稀疏图

二、最短路径

Dijkstra 算法：单源最短路径，适用于非负权图，时间 $O(n^2)$
Floyd 算法：各顶点间最短路径，适用于任意权图（无负权回路），时间 $O(n^3)$

关键区别MST 让“所有顶点连通且总边长最小”，但不保证任一顶点到源点距离最短；最短路径树只关心从源点出发的距离。

关键定义 ▾

概念	定义
生成树	连通图的极小连通子图，包含所有顶点和 $n-1$ 条边
最小生成树	边权之和最小的生成树（不唯一，但总权值唯一）
单源最短路径	从一个源点到其他所有顶点的最短路径
最短路径长度	两顶点间所有路径中边权之和最小的值
负权回路	回路中边权之和为负，此时最短路径不存在

常见考法 ▾

考点	说明
Prim / Kruskal 过程	逐步加入顶点 / 选边并判断是否成环
Dijkstra 过程	填写距离表和前驱表，逐步松弛
Floyd 过程	填写距离矩阵 $D$ 和路径矩阵 $P$
两种 MST 算法对比	Prim 适合稠密图，Kruskal 适合稀疏图
Dijkstra 负权限制	含负权边需用 Bellman-Ford

易错点 ▾

注意

Dijkstra 不能处理负权边（可处理负权顶点）
Floyd 不能处理负权回路
Prim 从任意顶点开始，结果总权值相同
Kruskal 每次选最短边需判断是否成环（并查集）
最小生成树不唯一，但总权值唯一
Dijkstra 中已确定最短路径的顶点不可再更新

核心结论 ▾

$n$ 个顶点的连通图，其生成树恰有 $n-1$ 条边
Prim 时间 $O(n^2)$，Kruskal 时间 $O(e\log e)$
Dijkstra 时间 $O(n^2)$，Floyd 时间 $O(n^3)$
Dijkstra 不适用于含负权边的图；Floyd 不适用于含负权回路的图
Floyd 状态转移方程：$$D^{(k)}[i][j] = \min\big(D^{(k-1)}[i][j],\; D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\big)$$
Prim 适合边多（稠密图），Kruskal 适合边少（稀疏图）

记忆卡片 ▾

Prim 和 Kruskal 的区别？

Prim 加点法 $O(n^2)$ 适合稠密图；Kruskal 加边法 $O(e\log e)$ 适合稀疏图。

Dijkstra 算法的限制？

不适用于含负权边的图。

Floyd 的时间复杂度？

$O(n^3)$，可求所有顶点对之间最短路径，支持负权边但不支持负权回路。

最小生成树有几条边？

$n$ 个顶点的 MST 恰好 $n-1$ 条。

MST 与最短路径树相同吗？

不同：MST 最小化全体边长和，最短路径树只最小化到源点的距离。

Floyd 的 k 循环在哪一层？

最外层（k 为中间顶点）。

交互动画 · MST vs 最短路径树（从 A） ▾

点击两种算法对比差异

MST 总权最小 vs 最短路径树到 A 距离最小

注意：MST 选的是 (A,D)(D,C)(C,B)(B,E) 总权 10；从 A 的最短路径树选 (A,D)(A,C)(A,B)(D,E)——两者边集不同，目标函数不同。

相关知识点

graph-traversal-and-applications adjacency-mulitlist-and-orthogonal topological-sort critical-path

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。