Floyd-Warshall算法（简称Floyd算法）是解决全源最短路径（All-Pairs Shortest Path）问题的经典动态规划算法。与Dijkstra算法需要运行V次才能求出所有顶点对的最短路径不同，Floyd算法只需一次三重循环即可解决。本文将深入剖析其动态规划思想，并用Java实现带路径记录的完整版本。
问题定义
给定一个带权有向图G=(V, E)，其中V是顶点集合，E是边集合，权重可以为正、负（但不能有负权环）。要求找出任意两个顶点之间的最短路径长度。
动态规划思想
Floyd算法的核心状态定义为：
dp[k][i][j] = 从顶点i到顶点j，只经过编号不超过k的顶点作为中间点时的最短路径长度
状态转移方程：
dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
即：从i到j的最短路径，要么不经过顶点k，要么经过顶点k（由i→k和k→j两段组成）。
由于dp[k]只依赖于dp[k-1]，可以用二维数组滚动优化，去掉第一维。
Java实现
import java.util.Arrays;
/**
* Floyd-Warshall算法实现
* 求解全源最短路径，支持负权边（不支持负权环）
*/
public class FloydWarshall {
private static final int INF = Integer.MAX_VALUE / 2; // 避免溢出的大数
int vertices;
int[][] dist; // 距离矩阵
int[][] next; // 路径记录矩阵，用于重构最短路径
public FloydWarshall(int vertices) {
this.vertices = vertices;
dist = new int[vertices][vertices];
next = new int[vertices][vertices];
// 初始化距离矩阵
for (int i = 0; i < vertices; i++) {
Arrays.fill(dist[i], INF);
dist[i][i] = 0; // 自身到自身距离为0
Arrays.fill(next[i], -1);
}
}
/**
* 添加有向边
* @param from 起点
* @param to 终点
* @param weight 权重
*/
public void addEdge(int from, int to, int weight) {
dist[from][to] = weight;
next[from][to] = to; // 记录下一步走向
}
/**
* Floyd-Warshall核心算法
* 时间复杂度: O(V³)
* 空间复杂度: O(V²)
*/
public void computeShortestPaths() {
// 三重循环：k为中间顶点，i为起点，j为终点
for (int k = 0; k < vertices; k++) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
// 如果经过k能缩短i到j的距离，则更新
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k]; // 更新路径：i→...→k→...→j
}
}
}
}
}
/**
* 检测图中是否存在负权环
* @return true表示存在负权环
*/
public boolean hasNegativeCycle() {
for (int i = 0; i < vertices; i++) {
if (dist[i][i] < 0) {
return true; // 顶点到自身的距离为负，说明存在负权环
}
}
return false;
}
/**
* 重构从start到end的最短路径
* @param start 起点
* @param end 终点
* @return 路径上的顶点列表，如果不可达返回空数组
*/
public int[] reconstructPath(int start, int end) {
if (dist[start][end] == INF) {
return new int[0]; // 不可达
}
// 先统计路径长度
int pathLength = 1;
int current = start;
while (current != end) {
current = next[current][end];
pathLength++;
}
// 填充路径
int[] path = new int[pathLength];
path[0] = start;
current = start;
int index = 1;
while (current != end) {
current = next[current][end];
path[index++] = current;
}
return path;
}
/**
* 打印距离矩阵
*/
public void printDistanceMatrix() {
System.out.println("=== 最短路径距离矩阵 ===");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
if (dist[i][j] == INF) {
System.out.print(" INF ");
} else {
System.out.printf(" %4d ", dist[i][j]);
}
}
System.out.println();
}
}
/**
* 传递闭包：判断任意两点是否可达
* 将距离矩阵改为布尔矩阵即可
*/
public boolean[][] transitiveClosure() {
boolean[][] reachable = new boolean[vertices][vertices];
// 初始化
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
reachable[i][j] = (i == j) || (dist[i][j] != INF);
}
}
// Floyd-Warshall变体
for (int k = 0; k < vertices; k++) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j]);
}
}
}
return reachable;
}
public static void main(String[] args) {
// 构建示例图（4个顶点）
FloydWarshall fw = new FloydWarshall(4);
fw.addEdge(0, 1, 5);
fw.addEdge(0, 3, 10);
fw.addEdge(1, 2, 3);
fw.addEdge(2, 3, 1);
fw.addEdge(3, 1, 2); // 形成环
fw.addEdge(1, 3, 9);
System.out.println("运行Floyd-Warshall算法...\n");
fw.computeShortestPaths();
if (fw.hasNegativeCycle()) {
System.out.println("图中存在负权环！");
return;
}
fw.printDistanceMatrix();
System.out.println("\n=== 具体路径示例 ===");
int[][] testPairs = {{0, 3}, {0, 2}, {3, 2}};
for (int[] pair : testPairs) {
int start = pair[0], end = pair[1];
int[] path = fw.reconstructPath(start, end);
System.out.printf("顶点 %d → 顶点 %d: 距离=%d, 路径=",
start, end, fw.dist[start][end]);
for (int i = 0; i < path.length; i++) {
System.out.print(path[i]);
if (i < path.length - 1) System.out.print(" → ");
}
System.out.println();
}
// 传递闭包
System.out.println("\n=== 传递闭包（可达性矩阵）===");
boolean[][] closure = fw.transitiveClosure();
for (int i = 0; i < fw.vertices; i++) {
for (int j = 0; j < fw.vertices; j++) {
System.out.print(closure[i][j] ? " 1 " : " 0 ");
}
System.out.println();
}
}
}
传递闭包的扩展应用
Floyd算法的框架可以轻松扩展为求解传递闭包（Transitive Closure）。传递闭包回答的问题是：对于图中的任意两个顶点i和j，是否存在一条从i到j的路径？
将距离矩阵的加法替换为逻辑或（OR），取最小值替换为逻辑与（AND），即可得到Warshall算法（Floyd算法的布尔版本）。
与其他最短路径算法的对比
| 算法 | 适用场景 | 时间复杂度 | 支持负权 | 全源/单源 |
|---|---|---|---|---|
| Dijkstra | 非负权图 | O((V+E)logV) | 否 | 单源 |
| Bellman-Ford | 含负权图 | O(VE) | 是 | 单源 |
| Floyd-Warshall | 稠密图全源 | O(V³) | 是 | 全源 |
| Johnson | 稀疏图全源 | O(V²logV + VE) | 是 | 全源 |
对于稠密图（E ≈ V²），Floyd的O(V³)比运行V次Dijkstra的O(V³logV)更优。对于稀疏图，Johnson算法更优。
动态规划的本质理解
Floyd算法是动态规划的教科书级范例：
- 最优子结构：全局最优解包含子问题的最优解。i到j的最短路径，如果经过k，则i→k和k→j也分别是最短路径。
- 重叠子问题：大量子问题被重复计算，用表格存储避免重复。
- 无后效性：状态转移只依赖于更小规模的状态，与如何达到该状态无关。
k作为最外层循环的顺序至关重要。它保证了在计算dp[k][i][j]时，dp[k-1][i][k]和dp[k-1][k][j]已经计算完成，符合动态规划的依赖顺序。
实际应用场景
- 网络路由：计算路由器之间的最短路径，用于OSPF等协议
- 社交网络分析：计算用户之间的最短连接路径（六度分隔理论）
- 交通规划：计算城市间最短通行时间和换乘方案
- 供应链优化：多仓库间的最优配送路径
复杂度分析
- 时间复杂度：O(V³)，三重循环，每个操作O(1)
- 空间复杂度：O(V²)，存储距离矩阵和路径矩阵
- 优化空间：如果只需要距离而不需要路径，可以省略next矩阵；如果图是稀疏的，使用邻接表加Johnson算法更优
常见错误与注意事项
- k循环必须在外层：如果k放在内层，会导致部分状态未更新就用于后续计算，结果错误
- INF的选择：应足够大但不能导致加法溢出。Integer.MAX_VALUE/2是安全的选择
- 负权环检测：运行完算法后检查dist[i][i]是否为负值
- 路径重构：需要额外维护next矩阵，不能仅凭距离矩阵推导路径
总结
Floyd-Warshall算法以极其简洁的三重循环实现了全源最短路径的计算，是动态规划思想的完美体现。其O(V³)的复杂度在稠密图上具有竞争力，且实现简单、易于扩展。理解Floyd算法不仅掌握了一个实用的图算法，更重要的是领会了如何将复杂问题分解为状态、定义状态转移、最终用填表的方式优雅地解决。
