总分类最小生成树 MSTPrim普利姆、Kruskal克鲁斯卡尔 作用无向连通带权图选出包含全部顶点、总权值最小的无环子图单源最短路径Dijkstra迪杰斯特拉 作用给定一个起点求该点到其余所有顶点最短路径仅支持非负权边多源全点对最短路径Floyd弗洛伊德 作用一次性求出任意两点之间最短路径支持负权边不能处理负权环一、Prim 普利姆算法最小生成树・加点法1. 核心思想贪心「加点」把顶点分为两个集合集合 S已选入最小生成树的顶点集合 V-S剩余未选顶点 初始任选一个顶点放入 S 循环每次从连接 S 与 V-S 的所有边中选权值最小的一条边把另一端顶点加入 S 直到 S 包含全部顶点结束。2. 适用场景稠密图顶点少、边多邻接矩阵存储最优无向连通带权图边权可正可负无负环要求3. 标准实现邻接矩阵408 手写模板核心数组dist[]dist[i] 顶点 i 到集合 S 的最小边权初始化起点入 S其余dist[i] 起点到i的边权无边设为∞循环 n-1 次总共选 n 个点已选 1 个 ① 在 V-S 中找到dist最小的顶点 u加入 S ② 用 u 更新所有不在 S 的顶点 vdist[v] min(dist[v], weight[u][v])4. 复杂度邻接矩阵实现\(O(n^2)\)n 为顶点数稠密图优势极大堆优化邻接表\(O(E\log n)\)稀疏图可用5. 优缺点✅ 稠密图效率极高无需预处理所有边 ❌ 稀疏图不如 Kruskal只能从顶点角度构建 MST6. 408 考点手工模拟表格计算 dist 数组与 Kruskal 对比选择场景无法处理不连通图必须连通图才有 MST二、Kruskal 克鲁斯卡尔算法最小生成树・加边法1. 核心思想贪心「加边」 并查集判环将图中所有边按权值从小到大排序依次遍历每条边(u,v,w)若 u、v 不在同一个连通分量并查集 find 根不同选中这条边合并两个集合加入 MST若 u、v 已连通舍弃否则形成环直到选出n-1条边MST 构造完成2. 适用场景稀疏图边数 E 远小于\(n^2\)邻接表存储边少、顶点多的图3. 核心工具并查集Union-Find两个操作find(x)查找顶点 x 所在集合根路径压缩优化union(x,y)合并两个顶点集合按秩合并优化4. 复杂度排序边\(O(E\log E)\)并查集操作近似\(O(1)\) 总复杂度\(O(E\log E)\)E 为边数5. 优缺点✅ 稀疏图极快代码简洁只需要边集合 ❌ 稠密图边数量巨大排序耗时不如 Prim6. 408 考点并查集手写实现手工模拟选边、判环过程森林生成不连通图会生成多棵最小生成森林Prim vs Kruskal 对比表格维度PrimKruskal贪心对象顶点加点边加边存储结构邻接矩阵稠密边集数组稀疏复杂度\(O(n^2)\)\(O(E\log E)\)最优场景稠密图稀疏图判环方式天然无环只连 S 内外并查集三、Dijkstra 迪杰斯特拉单源最短路径1. 核心思想贪心锁定最短顶点顶点划分S已确定源点最短路径的顶点V-S临时顶点 初始源点入 Sdist[]存源点到各点直接距离 循环每次选出 V-S 中 dist 最小顶点 u 加入 S 用 u 松弛更新所有邻接顶点 vdist[v] min(dist[v], dist[u]w(u,v))2. 硬性限制必考简答所有边权必须 ≥ 0不能存在负权边原因贪心一旦把顶点加入 S就认定最短路径固定负权边会导致后续出现更短路径无法回退更新结果错误。 负权单源替代算法Bellman-Ford / SPFA3. 实现方式朴素邻接矩阵\(O(n^2)\)适合稠密图小根堆优化优先队列\(O(E\log n)\)稀疏图标准写法4. 复杂度朴素版\(O(n^2)\)堆优化版\(O(E\log n)\)5. 408 高频坑点不能处理负权只算单源一次只能一个起点松弛操作公式记忆与 Floyd 区分使用场景。四、Floyd 弗洛伊德多源全点对最短路径1. 核心思想动态规划中间点中转松弛DP 状态定义dp[k][i][j]顶点 i 到 j只允许经过 0~k 号顶点中转的最短路径 空间优化二维数组dist[i][j]原地覆盖更新核心松弛公式万能公式plaintextdist[i][j] min( dist[i][j], dist[i][k] dist[k][j] )三层循环顺序中转点 k 最外层i、j 内层k0~n-1 枚举所有中间中转顶点i起点j终点2. 适用范围一次性求出任意两点间最短路径多源支持负权边但不能存在负权回路回路无限绕距离无限小顶点数量少n≤100顶点多则时间爆炸3. 初始化规则dist[i][i] 0自己到自己距离 0有直接边i→jdist[i][j] 边权无边dist[i][j] ∞4. 复杂度三层循环固定\(O(n^3)\)只适合小规模图5. 408 拓展考点判断负权环存在dist[i][i] 0说明 i 在负环内传递闭包改造把 min 换成或运算求可达性五、四大算法核心总对比表表格算法用途图类型要求能否负权核心思路最优场景时间复杂度Prim最小生成树 MST无向连通带权图允许负权贪心加点dist 数组稠密图\(O(n^2)\)Kruskal最小生成树 MST无向带权图可不连通允许负权贪心加边 并查集判环稀疏图\(O(E\log E)\)Dijkstra单源最短路径有向 / 无向图禁止负权边贪心锁定最短顶点单起点、无负权朴素\(O(n^2)\) / 堆\(O(E\log n)\)Floyd全点对最短路径有向 / 无向图允许负权禁负环动态规划中转松弛顶点少、求全部两点路径\(O(n^3)\)六、408 做题选择口诀求最小生成树 顶点少稠密图 → Prim边少稀疏图 → Kruskal只给一个起点求最短路径、无负权 → Dijkstra需要所有点互相之间最短路径、顶点数量少 → Floyd图存在负权边、单源最短路径 → 不能用 Dijkstra改用 Bellman-Ford
