Floyd-Warshall算法

Floyd-Warshall 的本质是一个三维状态压缩的动态规划：逐步允许更多中间点参与转移，最终得到所有点对最短路。

定义

Floyd-Warshall算法是一种用于求解所有节点对之间最短路径的动态规划算法，可以处理负权边。

图示例:
    0 --3-- 1
    |     / |
    5   2   1
    | /     |
    2 --4-- 3

最短路径矩阵:
    0   1   2   3
0 [ 0   3   5   4 ]
1 [ 2   0   2   1 ]
2 [ 5   2   0   4 ]
3 [ 6   1   4   0 ]

核心思路

• 动态规划：逐步考虑经过中间节点的路径
• 三重循环：枚举中间节点k、起点i、终点j
• 状态转移：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
• 多源最短路径：一次计算所有节点对的最短路径

为什么三重循环一定是 k -> i -> j

因为这题的 DP 含义是：

当前允许使用编号不超过 k 的点作为中间点。

所以必须先枚举“允许哪些中间点”，再枚举起点和终点。
外层的 k 实际上就是在一层层扩大状态空间。

复杂度分析

指标	复杂度	说明
时间复杂度	O(V³)	三重循环
空间复杂度	O(V²)	距离矩阵
适用场景	稠密图、小规模图	V较小时效率高

Go 代码

Go 实现

package main
 
import "math"
 
func FloydWarshall(graph [][]int, n int) [][]int {
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = math.MaxInt32
        }
    }
 
    // 初始化
    for i := 0; i < n; i++ {
        dist[i][i] = 0
        for j := 0; j < n; j++ {
            if graph[i][j] != 0 && graph[i][j] != math.MaxInt32 {
                dist[i][j] = graph[i][j]
            }
        }
    }
 
    // Floyd-Warshall
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != math.MaxInt32 &&
                    dist[k][j] != math.MaxInt32 &&
                    dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
 
    return dist
}

思路展开

动态规划思想

状态定义：

• dist[i][j][k]：从i到j，只经过节点0~k的最短路径

状态转移：

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

空间优化：

• 可以省略第三维，直接在原数组上更新

执行示例

初始图（邻接矩阵）:
    0   1   2   3
0 [ 0   3   ∞   5 ]
1 [ 2   0   ∞   ∞ ]
2 [ ∞   1   0   4 ]
3 [ ∞   ∞   2   0 ]

k=0（经过节点0）:
    0   1   2   3
0 [ 0   3   ∞   5 ]
1 [ 2   0   ∞   7 ]  // 1→0→3 = 2+5 = 7
2 [ ∞   1   0   4 ]
3 [ ∞   ∞   2   0 ]

k=1（经过节点0,1）:
    0   1   2   3
0 [ 0   3   ∞   5 ]
1 [ 2   0   ∞   7 ]
2 [ ∞   1   0   4 ]
3 [ ∞   ∞   2   0 ]

k=2（经过节点0,1,2）:
    0   1   2   3
0 [ 0   3   ∞   5 ]
1 [ 2   0   ∞   7 ]
2 [ ∞   1   0   4 ]
3 [ ∞   3   2   0 ]  // 3→2→1 = 2+1 = 3

k=3（经过节点0,1,2,3）:
    0   1   2   3
0 [ 0   3   7   5 ]  // 0→3→2 = 5+2 = 7
1 [ 2   0   9   7 ]  // 1→3→2 = 7+2 = 9
2 [ 6   1   0   4 ]  // 2→3→0 = 4+2 = 6
3 [ 5   3   2   0 ]  // 3→2→0 = 2+4 = 6, 但3→2→1→0 = 2+1+2 = 5

易错点

Floyd-Warshall 最容易写错的是初始化和状态转移顺序。

• 不可达边必须初始化成 inf。
• k 这一层不能和 i/j 的含义混掉。
• 如果题目要求检测负环，可以看最后是否有 dist[i][i] < 0。
• 它适合小规模全对全最短路，不适合大图暴力套。

经典题目

优缺点

优点

• ✅ 一次计算所有节点对最短路径
• ✅ 实现简单，代码简洁
• ✅ 可以处理负权边
• ✅ 适合稠密图

缺点

• ❌ 时间复杂度高 O(V³)
• ❌ 空间复杂度高 O(V²)
• ❌ 不适合大规模图
• ❌ 不如多次Dijkstra灵活

相关主题

• Dijkstra算法 - 单源最短路径
• Bellman-Ford算法 - 可处理负权边
• SPFA算法 - 队列优化版本
• 图算法 - 返回图算法总览

---

返回：图算法 | 算法学习导航