| 问题 | 要什么 | 算法 | 关键词 |
|---|---|---|---|
| 最小生成树 MST | 用 n-1 条边连通所有点，总权重最小 | Prim / Kruskal | 连通、总代价最小 |
| 最短路径 | 求两点之间路径权重和最小 | Dijkstra / Floyd | 点到点、路径最短 |
| 维度 | Prim | Kruskal | Dijkstra | Floyd |
|---|---|---|---|---|
| 解决 | 最小生成树 | 最小生成树 | 单源最短路径 | 多源最短路径 |
| 思想 | 贪心·加点 | 贪心·加边 | 贪心·松弛 | 动态规划 |
| 适用图 | 无向连通图 | 无向连通图 | 有向/无向，权非负 | 有向/无向，可含负权（无负权回路） |
| 复杂度 | O(n²) | O(e·log e) | O(n²) | O(n³) |
| 输出 | n-1 条边 | n-1 条边 | 起点到各点的距离 | 任意两点的距离矩阵 |
| 适合 | 稠密图 | 稀疏图 | 单起点查询 | 全对全查询 |
思想：从一个起点开始，每次从"已选集合连向外面的边"里挑最短的一条，把它连的点拉进来，直到所有点都进来。
手算步骤（从 A 出发）：
结果：选边 A-B、B-C、C-D，总权重 = 10+10+1 = 21
适用：稠密图；复杂度 O(n²)
思想：把所有边按权重从小到大排序，依次取边，只要不形成回路就要，取够 n-1 条为止。
手算步骤：
结果：选边 C-D、A-B、B-C，总权重 = 21（与 Prim 相同，MST 总权唯一）
适用：稀疏图；复杂度 O(e·log e)
思想：维护"起点到各点的当前最短距离"，每轮从未确定的点里选距离最小的那个确定为最终值，再用它去更新（松弛）邻居。
手算步骤（求 A 到各点）：
| 轮次 | 确定点 | A | B | C | D | 说明 |
|---|---|---|---|---|---|---|
| 初始 | — | 0 | ∞ | ∞ | ∞ | 起点 A 置 0 |
| 1 | A(0) | 0 | 10 | 15 | ∞ | 松弛：B=0+10，C=0+15 |
| 2 | B(10) | 0 | 10 | 15 | ∞ | 经 B 到 C = 10+10 = 20 > 15，不变 |
| 3 | C(15) | 0 | 10 | 15 | 16 | 经 C 到 D = 15+1 = 16 |
| 4 | D(16) | 0 | 10 | 15 | 16 | 结束 |
结果：A→B=10，A→C=15，A→D=16（路径 A-C-D）
思想：依次把每个点当作"中转站 k"，看能不能让其他两点间距离变短。三重循环，k 必须放最外层。
for k: for i: for j: d[i][j] = min(d[i][j], d[i][k] + d[k][j])
最终结果矩阵（任意两点间最短距离）：
| 从 \ 到 | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 10 | 15 | 16 |
| B | 10 | 0 | 10 | 11 |
| C | 15 | 10 | 0 | 1 |
| D | 16 | 11 | 1 | 0 |
读法：第 A 行第 D 列 = 16，即 A→D 最短 16，与 Dijkstra 结果一致（互相验证）。
适用：全对全查询；复杂度 O(n³)
| 易错点 | 正确说法 |
|---|---|
| Dijkstra 能算负权图吗 | 不能。贪心前提是"已确定的点不会被改小"，负权会打破它。含负权用 Floyd（或 Bellman-Ford） |
| Floyd 三重循环顺序 | k 必须在最外层（中转站）。写成 i,j,k 结果错误 |
| 四种算法谁能求最长路 | 都不行。最长路问题性质完全不同 |
| 最小生成树的边能推两点最短距离吗 | 不能。见上面 A→D=16 的例子 |
| MST 权值唯一吗 | 总权唯一，但选出的边集可能不唯一（等权边时） |
| Kruskal 如何判环 | 用并查集（Union-Find），两点已在同一集合则弃该边 |