任意两点最短路：Floyd 与复杂度分析

01 · 核心概念

Floyd 多源最短路与时间/空间复杂度

Floyd 多源最短路与时间/空间复杂度：Floyd 用 n×n 的矩阵存图：dist[i][j] 是 i 直达 j 的距离，自己到自己为 0，没有直达边用 float("inf") 表示无穷大。注意有向图里 dist[i][j] 与 dist[j][i] 是两回事。

02 · 语法与规则

先记住这 3 条，再开始写程序

04 · 逐步理解

每一步只解决一个问题

1. 01

   用邻接矩阵初始化

   Floyd 用 n×n 的矩阵存图：dist[i][j] 是 i 直达 j 的距离，自己到自己为 0，没有直达边用 float("inf") 表示无穷大。注意有向图里 dist[i][j] 与 dist[j][i] 是两回事。

   PYTHON⧉复制

   INF = float("inf")
   dist = [[0, 5, INF], [INF, 0, 2], [INF, INF, 0]]

2. 02

   三重循环：k 必须最外层

   核心就三行：枚举中转站 k，再枚举起点 i 和终点 j，若 i→k→j 比直达更近就更新。k 在最外层表示“允许经过前 k 个点中转”，顺序写反答案就错——这是 Floyd 最容易踩的坑。

   PYTHON⧉复制

   for k in range(n):
       for i in range(n):
           for j in range(n):

3. 03

   松弛判断与无穷大陷阱

   dist[i][j] > dist[i][k] + dist[k][j] 成立就更新。Python 的 inf 参与加法仍是 inf，比较不会出错；但在其他语言里要小心溢出。理解这一点，将来换语言也不慌。

   PYTHON⧉复制

   if dist[i][j] > dist[i][k] + dist[k][j]:
       dist[i][j] = dist[i][k] + dist[k][j]

4. 04

   算一笔复杂度账

   时间 O(n³)、空间 O(n²)。n = 100 时 10^6 次操作，飞快；n = 1000 时 10^9 次，Python 要跑几分钟。所以 Floyd 适合 n ≤ 200 左右的稠密小图，点多了要换回 Dijkstra。

5. 05

   算法选型决策表

   只问一个起点到所有点：Dijkstra（堆优化 O(m log n)）。问任意两点之间、且点数不多：Floyd（O(n³)）。要连通所有点且总代价最小：Kruskal（O(m log m)）。竞赛读题第一步：先看数据范围选算法。

6. 06

   空间复杂度同样会挂

   n×n 矩阵在 n = 10^5 时需要 10^10 个格子，内存直接爆掉。这就是为什么 Dijkstra 用邻接表（O(n+m)）而不是矩阵。估算内存：每个 int 约 28 字节，列表还有额外开销，大 n 务必用表。

05 · 练习与检验

自己写出来，才算真正学会