数据结构与算法 / 系统课时
Floyd-Warshall 算法
Floyd-Warshall 算法
Floyd-Warshall 用一个距离矩阵同时求出所有顶点对之间的最短路径。本课将从“是否允许某个中间点”这一状态出发,推导转移顺序,并实现距离计算、路径还原和负权环检测。
距离矩阵与路径还原
- 说明
k作为最外层循环的动态规划含义。 - 使用邻接矩阵计算全源最短距离并还原具体路径。
- 判断负权边、不可达顶点和负权环对结果的影响。
全源最短路何时适用
当系统需要频繁回答任意两点之间的最短距离,例如小规模路由表、站点换乘成本或模块依赖代价时,逐个源点运行单源算法会增加实现和调用成本。Floyd-Warshall 直接维护一个 矩阵,适合顶点数不大、图可能较稠密的场景。
图可以包含负权边,但不能把经过负权环的结果解释为有限最短路径。若最终存在 dist[i][i] < 0,说明顶点 i 位于或能够经过某个负权环返回自身。
按中间顶点推进矩阵
设 dist[i][j] 表示当前允许使用一组中间顶点时,从 i 到 j 的最短距离。处理顶点 k 时,每一对 (i, j) 只有两种选择:
- 不经过
k,保留dist[i][j]。 - 经过
k,候选距离为dist[i][k] + dist[k][j]。
因此转移为 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。k 必须放在最外层,因为一轮结束后,矩阵才完整表示“已经允许顶点 0 到 k 作为中间点”的状态。把 i 或 j 放到最外层会破坏这一阶段边界,难以保证原地更新仍符合动态规划定义。

算法需要三重循环,时间复杂度为 ;距离矩阵和路径矩阵的空间复杂度均为 。计算候选值前必须确认两段距离都可达,避免无穷大哨兵参与加法。
Java 实现与受负环影响的顶点对
下面的 Java 17 程序使用 next 矩阵记录路径的下一跳。每当经过 k 得到更短路径时,把 next[i][j] 更新为 next[i][k]。还原前先确认起点能否经负权环再到终点。若能,就可以反复经过负环以降低总成本,因此拒绝返回有限最短路径。其他不受该环影响的顶点对仍可还原。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FloydWarshallDemo {
private static final long INF = Long.MAX_VALUE / 4;
record Edge(int from, int to, int weight) {
}
record Result(long[][] distance, int[][] next, boolean hasNegativeCycle) {
}
static Result floydWarshall(int vertexCount, List<Edge> edges) {
long[][] distance = new long[vertexCount][vertexCount];
int[][] next = new int[vertexCount][vertexCount];
for (int i = 0; i < vertexCount; i++) {
Arrays.fill(distance[i], INF);
Arrays.fill(next[i], -1);
distance[i][i] = 0;
next[i][i] = i;
}
// 若存在平行边,只保留权重最小的一条。
for (Edge edge : edges) {
if (edge.weight() < distance[edge.from()][edge.to()]) {
distance[edge.from()][edge.to()] = edge.weight();
next[edge.from()][edge.to()] = edge.to();
}
}
// k 必须位于最外层,表示逐步扩大允许使用的中间顶点集合。
for (int k = 0; k < vertexCount; k++) {
for (int i = 0; i < vertexCount; i++) {
if (distance[i][k] == INF) {
continue;
}
for (int j = 0; j < vertexCount; j++) {
if (distance[k][j] == INF) {
continue;
}
long candidate = distance[i][k] + distance[k][j];
if (candidate < distance[i][j]) {
distance[i][j] = candidate;
next[i][j] = next[i][k];
}
}
}
}
boolean hasNegativeCycle = false;
for (int i = 0; i < vertexCount; i++) {
if (distance[i][i] < 0) {
hasNegativeCycle = true;
break;
}
}
return new Result(distance, next, hasNegativeCycle);
}
static List<Integer> reconstructPath(Result result, int from, int to) {
if (result.next()[from][to] == -1) {
return List.of();
}
for (int k = 0; k < result.distance().length; k++) {
if (result.distance()[k][k] < 0
&& result.distance()[from][k] != INF
&& result.distance()[k][to] != INF) {
throw new IllegalStateException("该顶点对受负权环影响,没有有限最短路径");
}
}
List<Integer> path = new ArrayList<>();
int current = from;
path.add(current);
while (current != to) {
current = result.next()[current][to];
path.add(current);
}
return path;
}
static void printMatrix(long[][] matrix) {
for (long[] row : matrix) {
for (int j = 0; j < row.length; j++) {
String value = row[j] == INF ? "INF" : Long.toString(row[j]);
System.out.print(value);
System.out.print(j + 1 == row.length ? System.lineSeparator() : " ");
}
}
}
static String formatPath(List<Integer> path) {
if (path.isEmpty()) {
return "不可达";
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
if (i > 0) {
builder.append(" -> ");
}
builder.append(path.get(i));
}
return builder.toString();
}
public static void main(String[] args) {
List<Edge> edges = List.of(
new Edge(0, 1, 5),
new Edge(0, 3, 10),
new Edge(1, 2, 3),
new Edge(2, 3, 1),
new Edge(3, 0, 2)
);
Result result = floydWarshall(4, edges);
System.out.println("最短距离矩阵:");
printMatrix(result.distance());
System.out.println("0 到 3 的最短路径: "
+ formatPath(reconstructPath(result, 0, 3)));
System.out.println("存在负权环: " + result.hasNegativeCycle());
}
}将代码保存为 FloydWarshallDemo.java,然后运行:
javac FloydWarshallDemo.java
java FloydWarshallDemo读矩阵和下一跳
最短距离矩阵:
0 5 8 9
6 0 3 4
3 8 0 1
2 7 10 0
0 到 3 的最短路径: 0 -> 1 -> 2 -> 3
存在负权环: false用断边和负权环验证边界
最常见的错误是把循环顺序写成 i-j-k,这会让原地矩阵不再严格对应“逐步开放中间顶点”的阶段。另一个错误是没有初始化 dist[i][i] = 0,导致自身距离和负权环检测失真。遇到平行边时也应保留最小边权,而不是让后读入的边无条件覆盖前一条。
练习 1:删除边 3 -> 0,观察矩阵中的 INF,并验证从 3 到 2 的路径返回“不可达”。
练习 2:加入边 3 -> 1,权重为 -5,分析哪些对角线元素会变为负数,并验证程序报告负权环。再调用 reconstructPath(result, 0, 3),应抛出说明没有有限最短路径的异常。另加一个与负权环隔离的顶点,验证从该顶点到自身仍可返回只含自身的路径。
可达、不可达和无有限最短路
- Floyd-Warshall 通过逐步开放中间顶点,统一求解所有顶点对最短路径。
k-i-j循环顺序维护了原地动态规划更新的阶段语义。next矩阵支持路径还原,对角线负值用于检测负权环。
从路径代价转向生成树
下一阶段将把“路径代价最小”与“连接全部顶点的总边权最小”区分开,继续学习最小生成树的建模方式、贪心选择和正确性依据。