如何用Floyd-Warshall算法获取顶点1到10的所有等权最短路径？

嘿，看你已经搞定了统计顶点1到10的最短路径总数，现在要扩展成获取所有权重相同的最短路径对吧？咱们基于你现有的Floyd-Warshall代码框架来改，其实核心就是维护好三个关键矩阵，再调整循环里的更新逻辑就行。

先理清楚核心思路 #

Floyd-Warshall原本是求所有点对最短路径的，要统计权重一致的最短路径，我们得同时维护三个矩阵：

• dist矩阵：存储顶点i到j的最短路径权重
• count矩阵：存储i到j的最短路径总数
• path矩阵：用来回溯具体的路径（如果需要输出路径而非仅计数的话）

对现有代码的修改方案 #

你的代码已经有了adj邻接矩阵、path和count的雏形，咱们一步步完善：

1. 先把矩阵初始化做好 #

首先得正确初始化这三个矩阵，处理好直接相连、不可达和自环的情况：

public static void init(int[][] adj, int[][] dist, int[][] count, int[][] path) {
    int n = adj.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = adj[i][j];
            // 初始化计数：自己到自己算1条路径；直接相连的边算1条；不可达的话计数为0
            if (i == j) {
                count[i][j] = 1;
                path[i][j] = -1; // 标记没有中间节点
            } else if (adj[i][j] != Integer.MAX_VALUE) {
                count[i][j] = 1;
                path[i][j] = i; // 直接路径的前驱就是起点
            } else {
                count[i][j] = 0;
                path[i][j] = -1;
            }
        }
    }
}

2. 修改核心循环的更新逻辑 #

原有的三层循环里，我们要根据三种情况更新计数和路径：

• 情况1：经过k节点的路径比当前最短路径更短 → 更新距离，把计数重置为count[i][k] * count[k][j]（i到k的路径数乘k到j的路径数）
• 情况2：经过k节点的路径和当前最短路径权重一样 → 把计数累加count[i][k] * count[k][j]
• 情况3：经过k节点的路径更长 → 啥也不用做

修改后的核心循环代码：

public static void floydWarshall(int[][] adj, int[][] dist, int[][] count, int[][] path) {
    int n = adj.length;
    init(adj, dist, count, path);
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 跳过不可达的情况，避免整数溢出
                if (dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE) {
                    continue;
                }
                
                int newDist = dist[i][k] + dist[k][j];
                if (newDist < dist[i][j]) {
                    // 找到更短的路径，更新距离和计数
                    dist[i][j] = newDist;
                    count[i][j] = count[i][k] * count[k][j];
                    path[i][j] = k; // 记录中间节点k
                } else if (newDist == dist[i][j] && i != j) {
                    // 找到权重相同的最短路径，累加计数
                    count[i][j] += count[i][k] * count[k][j];
                    // 要是需要记录所有路径，这里的path矩阵得改成存所有可能的中间节点，比如用List数组
                }
            }
        }
    }
}

3. 回溯获取具体的所有路径 #

如果需要输出顶点1到10的每一条最短路径，得基于path矩阵递归回溯。注意哦，如果存在多条路径，path矩阵得存所有可能的中间节点，不然只能拿到一条路径：

public static void findAllPaths(int[][] path, int start, int end, List<Integer> currentPath, List<List<Integer>> allPaths) {
    if (start == end) {
        allPaths.add(new ArrayList<>(currentPath));
        return;
    }
    int mid = path[start][end];
    if (mid == -1) {
        // 直接路径，把终点加进去存起来
        currentPath.add(end);
        allPaths.add(new ArrayList<>(currentPath));
        currentPath.remove(currentPath.size() - 1);
        return;
    }
    // 递归遍历start到mid、mid到end的所有路径
    findAllPaths(path, start, mid, currentPath, allPaths);
    currentPath.add(mid);
    findAllPaths(path, mid, end, currentPath, allPaths);
    currentPath.remove(currentPath.size() - 1);
}

调用示例（适配顶点1-10） #

注意如果你的顶点是1-based编号（比如顶点1对应数组索引1），初始化邻接矩阵的时候要对应上：

public static void main(String[] args) {
    int n = 11; // 用索引1-10对应顶点1-10，索引0不用
    int[][] adj = new int[n][n];
    // 初始化邻接矩阵：自己到自己权重0，其他默认不可达（设为Integer.MAX_VALUE）
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            adj[i][j] = (i == j) ? 0 : Integer.MAX_VALUE;
        }
    }
    // 这里添加你的边，比如顶点1到顶点2权重为3：adj[1][2] = 3;
    
    int[][] dist = new int[n][n];
    int[][] count = new int[n][n];
    int[][] path = new int[n][n];
    
    floydWarshall(adj, dist, count, path);
    
    // 输出顶点1到10的最短路径总数
    System.out.println("顶点1到10的最短路径总数：" + count[1][10]);
    
    // 输出所有具体路径
    List<List<Integer>> allPaths = new ArrayList<>();
    List<Integer> currentPath = new ArrayList<>();
    currentPath.add(1); // 起点加入当前路径
    findAllPaths(path, 1, 10, currentPath, allPaths);
    
    System.out.println("所有最短路径：");
    for (List<Integer> p : allPaths) {
        System.out.println(p);
    }
}

几个要注意的点 #

• 处理不可达的情况时，别用Integer.MAX_VALUE直接相加，会溢出，所以循环里先判断是否不可达
• 如果图里有负权边但没有负权环，算法还是能用；但有负权环的话就不存在最短路径了
• 要是需要完整记录所有路径，path矩阵不能只存单个中间节点，得改成List<Integer>[][]类型，这样才能存所有可能的中间节点分支

内容的提问来源于stack exchange，提问作者Tuan Pham