Floyd-Warshall 算法如何求多源最短路径？适合什么场景？

简化版

Floyd-Warshall 用动态规划求任意两点之间的最短路径。

它枚举中转点 k，尝试用 k 改善 i -> j 的距离：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

复杂度是 O(V^3)，空间是 O(V^2)，适合点数不大、需要多源最短路径的稠密图或全局查询场景。

详细版

Floyd 的状态可以理解为：只允许使用编号不超过 k 的点作为中转点时，i 到 j 的最短距离。

实现中通常用三重循环原地更新：

for k in 0..V-1:
  for i in 0..V-1:
    for j in 0..V-1:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

算法	类型	适合
Dijkstra	单源	非负权、大图
Bellman-Ford	单源	有负权边、负环检测
Floyd	多源	点数较小、全局最短路

它可以处理负权边，但不能处理有负环的最短路径问题。

完整版教学

1. Floyd 解决的是什么问题

Dijkstra 和 Bellman-Ford 通常从一个源点出发，求它到其他点的最短路径。

Floyd-Warshall 解决的是所有点对之间的最短路径：

for every i, j: shortestPath(i, j)

如果业务需要频繁问任意两个点距离，提前跑 Floyd 很方便。

2. 动态规划状态怎么理解

Floyd 的核心是中转点限制。

定义：

dist[i][j] = 当前允许的中转点集合下，i 到 j 的最短距离

当枚举到中转点 k 时，有两种选择：

不经过 k，保持原距离；
经过 k，距离变成 dist[i][k] + dist[k][j]。

Floyd 的三重循环不是暴力乱试，而是在逐步扩大允许的中转点集合。

3. 为什么 k 要放在最外层

k 表示当前新允许加入的中转点。

只有把 k 放在最外层，才能保证更新 dist[i][j] 时，dist[i][k] 和 dist[k][j] 已经是在只使用前面中转点的最优结果。

如果循环顺序乱了，动态规划语义会被破坏。

4. 初始化怎么做

初始化通常是：

条件	初始值
`i == j`	`0`
有边 `i -> j`	边权
没有边	`INF`

如果有多条边连接同一对点，取最小边权。

dist[u][v] = min(dist[u][v], w)

无向图要同时设置 dist[u][v] 和 dist[v][u]。

5. 能否处理负权边和负环

Floyd 可以处理负权边，因为它不依赖 Dijkstra 那种贪心确定性。

但如果存在负环，相关路径可以无限变小，最短路径没有有限答案。

跑完后可以通过：

dist[i][i] < 0

判断是否存在可影响的负环。

6. 复杂度为什么比较高

Floyd 是三重循环：

V * V * V = O(V^3)

空间需要一个 V x V 矩阵：

O(V^2)

所以它不适合点数特别大的图。比如 V = 10000 时，矩阵空间就已经很难接受。

7. 什么时候选 Floyd

可以这样判断：

场景	是否适合 Floyd
点数几百	比较适合
要查任意两点距离	适合
稠密图	可以考虑
大规模稀疏图	通常不适合
单源查询	Dijkstra 或 Bellman-Ford 更合适

如果只是从一个源点出发，没必要跑全局三重循环。

8. 常见误区与追问

误区：Floyd 是 BFS 的变体。 Floyd 是动态规划，多用于带权图的任意点对最短路径。
误区：k 可以放在任意一层循环。 k 的外层顺序承载动态规划语义，不能随便换。
误区：Floyd 适合所有图。 它的 O(V^3) 和 O(V^2) 成本很高，点数大时不合适。
追问：如何检测负环？ 跑完后检查是否存在 dist[i][i] < 0。
追问：为什么可以原地更新？ 因为按 k 分阶段扩展中转点集合，当前阶段只依赖已经允许的中转结果。

简化版

详细版