数据结构与算法 / 系统课时

Floyd-Warshall 算法

Floyd-Warshall 算法

Floyd-Warshall 用一个距离矩阵同时求出所有顶点对之间的最短路径。本课将从“是否允许某个中间点”这一状态出发,推导转移顺序,并实现距离计算、路径还原和负权环检测。

距离矩阵与路径还原

  • 说明 k 作为最外层循环的动态规划含义。
  • 使用邻接矩阵计算全源最短距离并还原具体路径。
  • 判断负权边、不可达顶点和负权环对结果的影响。

全源最短路何时适用

当系统需要频繁回答任意两点之间的最短距离,例如小规模路由表、站点换乘成本或模块依赖代价时,逐个源点运行单源算法会增加实现和调用成本。Floyd-Warshall 直接维护一个 ∣V∣×∣V∣|V| \times |V| 矩阵,适合顶点数不大、图可能较稠密的场景。

图可以包含负权边,但不能把经过负权环的结果解释为有限最短路径。若最终存在 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 放到最外层会破坏这一阶段边界,难以保证原地更新仍符合动态规划定义。

Floyd-Warshall 中间点扩展与矩阵更新

算法需要三重循环,时间复杂度为 O(∣V∣3)O(|V|^3);距离矩阵和路径矩阵的空间复杂度均为 O(∣V∣2)O(|V|^2)。计算候选值前必须确认两段距离都可达,避免无穷大哨兵参与加法。

Java 实现与受负环影响的顶点对

下面的 Java 17 程序使用 next 矩阵记录路径的下一跳。每当经过 k 得到更短路径时,把 next[i][j] 更新为 next[i][k]。还原前先确认起点能否经负权环再到终点。若能,就可以反复经过负环以降低总成本,因此拒绝返回有限最短路径。其他不受该环影响的顶点对仍可还原。

java
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,然后运行:

bash
javac FloydWarshallDemo.java
java FloydWarshallDemo

读矩阵和下一跳

text
最短距离矩阵:
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 矩阵支持路径还原,对角线负值用于检测负权环。

从路径代价转向生成树

下一阶段将把“路径代价最小”与“连接全部顶点的总边权最小”区分开,继续学习最小生成树的建模方式、贪心选择和正确性依据。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Floyd-Warshall 算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通