Floyd-Warshall（弗洛伊德）算法 考研笔记

一、算法概述

1.1 核心思想

Floyd算法是一种多源最短路径算法，基于动态规划思想，用于求解图中任意两个顶点之间的最短路径。

核心原理： 通过逐次引入每个顶点 k 作为”中间节点”，不断更新所有顶点对 (i, j) 之间的最短路径长度。

状态转移：

  • 初始状态 D⁰： 只允许直接路径（邻接矩阵）
  • 第k次迭代 Dᵏ： D$i$$j$ 表示从 i 到 j 只允许经过集合 {1, 2, …, k} 中的顶点作为中间节点的最短路径长度
  • 最终状态 Dⁿ： 任意两点间的最短路径值

1.2 算法特点

特性 描述
算法类型 多源最短路径，动态规划
时间复杂度 O(V³)，三层循环
空间复杂度 O(V²)，需存储距离矩阵和路径矩阵
适用图 有向图、无向图均可
权值限制 可处理负权边，但不能处理负权环
优点 代码简洁，一次运行得到所有顶点对最短路径
缺点 时间复杂度高，不适合顶点数很多的图

二、算法步骤详解

2.1 第一步：初始化邻接矩阵

核心公式：

1
D[i][j] = min(D[i][j], D[i][k] + D[k][j])

迭代规则（第k次迭代）

（1）照抄部分
  • 主对角线第k行整行照抄
  • 主对角线第k列整列照抄
  • 该行列中为∞的元素，其对应的行和列也照抄
  • 主对角线元素（0）始终不变
（2）更新部分

对于其他位置的元素 (i, j)：

  • 比较： 原值 vs (i到k的距离 + k到j的距离)
  • 更新规则： 取较小值
  • 角标更新： 若更新，则合并路径角标

三、考研重点总结

3.1 必背核心

  1. 核心公式： $D{ij} = \min(D{ij},\ D{ik} + D{kj})$
  2. 时间复杂度： O(V³)
  3. 迭代顺序： k 循环在最外层（逐步引入中间点）
  4. 负权处理： 可处理负权边，不能处理负权环

3.2 与其他算法对比

特性 Floyd Dijkstra Bellman-Ford
路径类型 多源 单源 单源
时间复杂度 O(V³) O(V²) 或 O(ElogV) O(VE)
负权边 ✓ ✗ ✓
负权环 ✗ ✗ 可检测
实现难度 简单 中等 中等
适用场景 稠密图小规模 无负权单源 有负权单源

3.3 手算技巧

  1. 严格按照迭代规则：先照抄，后更新
  2. 遇到∞跳过计算
  3. 角标记录完整路径（便于验证）
  4. 对角线始终为0