illegalCreed

中文

English

中文

English

Appearance

Floyd-Warshall 与应用场景 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • Floyd-Warshall 核心：全源最短路 DP——外层枚举「中转点 k」，内层枚举所有点对 (i,j)，dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])，即「i→j 的最短路要么不经过 k，要么经过 k（=i→k+k→j）」。
  • 状态转移：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])——只用前 k 个点做中转时 i→j 的最短路。空间可降维到 dp[i][j]（原地更新，因为 dp[k][i][k]=dp[k-1][i][k]、dp[k][k][j]=dp[k-1][k][j]）。
  • 复杂度：O(V³) 时间、O(V²) 空间——三重循环，与图密度无关；只适合 V 较小（≤500） 的图，大图超时。
  • 适用场景：全源最短路、稠密小图、求传递闭包（可达性）、多次任意两点查询；能处理负权（不能有负环）。
  • 不能判负环吗：能——跑完后若 dp[i][i] < 0 说明存在经过 i 的负环（自己到自己变负），但通常用 BF/SPFA 判更直接。
  • 传递闭包：把 Floyd 的 min/+ 换成 ||/&&——reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])，一次求所有点对的可达性。
  • 初始化关键：dp[i][i]=0（自己到自己）、dp[i][j]=w(i,j)（有边）、dp[i][j]=+∞（无边）；对角线必须 0，否则结果错。
  • 循环顺序：中转点 k 必须在最外层——这是 DP「依次允许更多中转点」的阶段划分；写错顺序（k 在内层）会得到错误结果。
  • 选型决策：全源 + 稠密 + V 小 → Floyd；全源 + 稀疏 + V 大 → 跑 V 次 Dijkstra；单源 → Dijkstra/BF；要判负环 → BF/SPFA。
  • 路径还原：用 nxt[i][j] 记录「i→j 当前最短路的第一跳」，松弛成功时更新 nxt[i][j]=nxt[i][k]，最后从 i 沿 nxt[i][j] 跳到 j。
  • 易错：k 写在内层；对角线初始化非 0；忘判负环（dp[i][i]<0）；用 Floyd 跑大图超时。

一、Floyd-Warshall：三重循环 DP 求全源 ​

算法思想 ​

Floyd 的思路是动态规划：逐步放宽「允许的中转点集合」。令 dp[k][i][j] 表示「只允许用前 k 个点（编号 1..k）做中转时，i→j 的最短路」，则有：

dp[k][i][j] = min(
    dp[k-1][i][j],              // 不经过 k
    dp[k-1][i][k] + dp[k-1][k][j]  // 经过 k：i→k→j
)

直觉：引入中转点 k 后，i→j 要么不走 k（用旧答案），要么走 k（拆成 i→k + k→j，两段都用前 k−1 个点做中转）。当 k 从 1 枚举到 V，dp[V][i][j] 就是允许所有点做中转的真实最短路。

空间优化：降维到二维 ​

观察 dp[k][i][k] = dp[k-1][i][k]（i→k 不可能经过 k 做中转，会成环），同理 dp[k][k][j]=dp[k-1][k][j]。所以原地更新时 dp[i][k] 和 dp[k][j] 不会被本轮改变，可以安全降维：

for k = 1 to V:                  // 中转点在最外层！
    for i = 1 to V:
        for j = 1 to V:
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

关键：中转点 k 必须在最外层。这是 DP「按阶段（允许的中转点数）递推」的要求——若 k 在内层，会用到「同阶段、未更新完」的错误值。

代码实现 ​

js
function floyd(graph, n) {
  // graph: 邻接矩阵，graph[i][j] = 权值或 Infinity
  const dp = graph.map(row => row.slice());   // 拷贝
  const nxt = Array.from({length: n}, (_, i) =>
    Array.from({length: n}, (_, j) => j));    // 第一跳初始为 j
  for (let k = 0; k < n; k++) {               // 中转点在最外层
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dp[i][k] + dp[k][j] < dp[i][j]) {
          dp[i][j] = dp[i][k] + dp[k][j];
          nxt[i][j] = nxt[i][k];              // 第一跳改为 i→k 的第一跳
        }
      }
    }
  }
  // 判负环：对角线变负
  for (let i = 0; i < n; i++)
    if (dp[i][i] < 0) return { hasNegCycle: true };
  return { dp, nxt, hasNegCycle: false };
}

复杂度与适用边界 ​

  • 时间：O(V³)——三重循环，固定开销，与边数 E 无关。
  • 空间：O(V²)——存邻接矩阵 / dp 矩阵。
  • 适用：V ≤ 几百（V=500 时 1.25×10⁸ 次，可接受；V=1000 时 10⁹ 次，吃力；V=2000 基本超时）。
  • 能处理负权（但图不能含可达负环，否则最短路无定义），不能像 BF 那样在求路时优雅判负环，但 dp[i][i]<0 能事后检测。

二、传递闭包：Floyd 的变种 ​

把 Floyd 的「min + 加法」换成「|| + &&」，就得到求传递闭包（任意两点是否可达）的算法：

// reach[i][j] = true 表示 i 可达 j
初始化：reach[i][i]=true；reach[i][j]=true（若有边 i→j）
for k = 1 to V:
    for i = 1 to V:
        for j = 1 to V:
            reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])
  • 用途：求「所有点对的可达性」——如类继承关系、依赖关系的传递闭包、判断图中任意两点是否连通。
  • 复杂度：O(V³)，可用位运算优化（每行用一个 bitset，| 运算一次处理 64 个点）降到 O(V³/64)。
  • 与最短路的关系：传递闭包是「只关心能不能到、不关心距离」的退化版 Floyd。

三、四算法选型决策表 ​

最短路径的选型是面试高频考点，按「问题形态 + 权限制 + 图规模」三步决策：

场景权限制图规模首选算法复杂度
单源最短路非负权任意Dijkstra（堆优化）O((V+E)logV)
单源最短路可负权任意Bellman-FordO(VE)
单源最短路可负权求快（不怕被卡）SPFA平均 O(E)
判负环可负权任意Bellman-Ford / SPFAO(VE)
全源最短路任意（无负环）稠密 / V 小（≤500）Floyd-WarshallO(V³)
全源最短路非负权稀疏 / V 大跑 V 次 DijkstraO(V(V+E)logV)
任意两点可达性—V 小Floyd 传递闭包O(V³)

选型决策树 ​

要判负环吗？
├─ 是 → Bellman-Ford / SPFA
└─ 否
   └─ 单源还是全源？
      ├─ 单源
      │  └─ 有负权吗？
      │     ├─ 是 → Bellman-Ford / SPFA
      │     └─ 否 → Dijkstra（堆优化）
      └─ 全源
         └─ 图稠密吗？V 小吗？
            ├─ 是 → Floyd-Warshall
            └─ 否（稀疏大图）→ 跑 V 次 Dijkstra

易踩的坑 ​

  • Dijkstra 遇负权算错：必须换 BF/SPFA，别侥幸。
  • Floyd 跑大图超时：V > 1000 别用 Floyd，改「V 次 Dijkstra」。
  • SPFA 被卡成 O(VE)：竞赛有专门卡 SPFA 的数据，求稳用 Dijkstra（非负权）或 BF。
  • Floyd 循环顺序写错：k 必须最外层，否则用错阶段的值。
  • BF 忘判第 V 轮：漏判负环会得到错误的最短路值（实际是 −∞）。

交互演示 ​

下一步 ​

至此四种最短路算法都讲完了。最后用一份复杂度对比表 + 代码模板 + 选型决策树 + 易错点清单收尾，作为查阅手册，见参考。