从邻接矩阵到路径还原：Floyd算法Java实战与LeetCode应用指南

在解决图论中的最短路径问题时，我们常常会想到Dijkstra算法。但当需要计算图中所有节点对之间的最短路径时，Floyd算法凭借其简洁的三重循环实现和动态规划思想，成为了工程师工具箱中的必备利器。本文将带您从零开始构建一个完整的Floyd算法工具类，不仅实现基本的最短距离计算，更深入探讨如何还原具体路径，最后与LeetCode真题结合，打造算法学习到应用的完整闭环。

1. 理解Floyd算法的核心思想

Floyd算法本质上是一种基于动态规划的多源最短路径算法。想象一下城市之间的公路网，我们想要知道任意两座城市之间的最短行车距离。Floyd算法的精妙之处在于，它通过逐步引入"中转站"的概念，系统地比较直达和经中转的路线，最终得出全局最优解。

算法的核心在于这个递推关系：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

其中k就是我们逐步引入的中转节点。这个看似简单的公式，却蕴含着动态规划的精华——将大问题分解为重叠子问题，并通过记忆化存储中间结果。

与Dijkstra算法相比，Floyd具有以下特点：

特性	Floyd算法	Dijkstra算法
适用场景	多源最短路径	单源最短路径
时间复杂度	O(V³)	O(E + VlogV)
处理负权边	可以	不可以
实现复杂度	三重循环，代码简单	需要优先队列，实现较复杂

在实际工程中，当图的规模不大（V<500）时，Floyd算法往往是首选，因为它的实现简单直接，且能一次性解决所有节点对的问题。

2. 基础实现：邻接矩阵与距离计算

让我们从最基础的实现开始。在Java中，我们通常用邻接矩阵来表示图结构。下面是一个完整的Floyd算法实现，包含详细的初始化过程：

public class FloydAlgorithm {
    private static final int INF = Integer.MAX_VALUE;
    
    public int[][] computeShortestPaths(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        
        // 初始化距离矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        // 三重循环核心逻辑
        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] != INF && dist[k][j] != INF 
                        && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        return dist;
    }
}

注意：在实际应用中，INF的值应根据具体场景设置，避免整数溢出。比如可以设置为比最大可能路径稍大的值。

测试这个基础实现时，我们可以构建一个典型的图结构：

int[][] graph = {
    {0, 5, INF, 10},
    {INF, 0, 3, INF},
    {INF, INF, 0, 1},
    {INF, INF, INF, 0}
};

FloydAlgorithm floyd = new FloydAlgorithm();
int[][] shortestPaths = floyd.computeShortestPaths(graph);

这个基础版本虽然能计算出最短距离，但缺乏路径信息。在实际应用中，我们往往不仅需要知道距离，还需要知道具体的路径走向。

3. 进阶实现：路径还原与可视化

为了还原具体路径，我们需要引入一个前驱矩阵 path ，记录每个节点对之间的中转节点。下面是增强版的实现：

public class EnhancedFloyd {
    private static final int INF = Integer.MAX_VALUE;
    
    public static class Result {
        public int[][] distances;
        public int[][] paths;
        
        public Result(int[][] distances, int[][] paths) {
            this.distances = distances;
            this.paths = paths;
        }
    }
    
    public Result computeShortestPathsWithDetails(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        int[][] path = new int[n][n];
        
        // 初始化距离矩阵和路径矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
                path[i][j] = (graph[i][j] != INF && i != j) ? j : -1;
            }
        }
        
        // 三重循环核心逻辑
        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] != INF && dist[k][j] != INF 
                        && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = path[i][k]; // 关键修改点
                    }
                }
            }
        }
        
        return new Result(dist, path);
    }
    
    public static List<Integer> reconstructPath(int from, int to, int[][] paths) {
        if (paths[from][to] == -1) return Collections.emptyList();
        
        List<Integer> path = new ArrayList<>();
        path.add(from);
        while (from != to) {
            from = paths[from][to];
            path.add(from);
        }
        return path;
    }
}

使用这个增强版实现，我们不仅能得到距离，还能还原具体路径：

EnhancedFloyd floyd = new EnhancedFloyd();
EnhancedFloyd.Result result = floyd.computeShortestPathsWithDetails(graph);

// 获取从节点0到节点3的路径
List<Integer> path = EnhancedFloyd.reconstructPath(0, 3, result.paths);
System.out.println("Path: " + path); // 输出类似 [0, 1, 2, 3]

路径还原的实现要点：

1. path[i][j] 存储的是从i到j的最短路径上，i的下一个节点
2. 当发现更短路径时，更新 path[i][j] 为 path[i][k]
3. 通过回溯 path 矩阵，可以重建完整路径

4. 性能优化与边界处理

在实际工程应用中，我们需要考虑一些优化和边界情况：

优化技巧：

• 提前终止：如果 dist[i][k] 已经是INF，可以跳过内层循环
• 并行化：最外层k循环可以并行处理，因为每次迭代是独立的
• 空间优化：可以原地修改距离矩阵，减少内存使用

常见边界情况处理：

// 检查负权环
public boolean hasNegativeCycle(int[][] dist) {
    for (int i = 0; i < dist.length; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

// 处理大数相加溢出
private int safeAdd(int a, int b) {
    if (a == INF || b == INF) return INF;
    long sum = (long)a + b;
    return sum > INF ? INF : (int)sum;
}

内存优化版本（适合大规模图）：

public int[][] computeShortestPathsOptimized(int[][] graph) {
    int n = graph.length;
    int[][] dist = new int[n][];
    // 复制原始图
    for (int i = 0; i < n; i++) {
        dist[i] = Arrays.copyOf(graph[i], n);
    }
    
    for (int k = 0; k < n; k++) {
        int[] distK = dist[k]; // 缓存行
        for (int i = 0; i < n; i++) {
            int[] distI = dist[i];
            if (distI[k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (distK[j] != INF && distI[j] > distI[k] + distK[j]) {
                    distI[j] = distI[k] + distK[j];
                }
            }
        }
    }
    return dist;
}

5. LeetCode实战：1334.阈值距离内邻居最少的城市

让我们将Floyd算法应用到LeetCode 1334题。题目要求找到在给定距离阈值内可到达城市最少的城市，这正是Floyd算法的典型应用场景。

解题思路：

1. 使用Floyd算法计算所有城市对之间的最短距离
2. 对于每个城市，统计在阈值距离内的可到达城市数量
3. 找出可到达城市数量最少的城市

完整解决方案：

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        // 初始化邻接矩阵
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[i][i] = 0;
        }
        
        // 构建图
        for (int[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
            dist[edge[1]][edge[0]] = edge[2];
        }
        
        // Floyd算法核心
        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) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        // 寻找最优城市
        int minCount = n;
        int result = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] <= distanceThreshold) {
                    count++;
                }
            }
            if (count <= minCount) {
                minCount = count;
                result = i;
            }
        }
        
        return result;
    }
}

复杂度分析：

• 时间复杂度：O(n³)，由Floyd算法主导
• 空间复杂度：O(n²)，存储距离矩阵

类似可应用Floyd算法的LeetCode题目：

• 743. Network Delay Time
• 1462. Course Schedule IV
• 1617. Count Subtrees With Max Distance Between Cities

6. 工程实践中的经验分享

在实际项目中使用Floyd算法时，有几个经验值得分享：

1. 预处理的重要性 ：在构建邻接矩阵时，确保对角元素为0（节点到自身的距离），非连接边的INF值要统一处理。我曾经遇到一个bug，就是因为忘记初始化对角线元素，导致算法计算出错。

2. 路径还原的调试技巧 ：当路径还原出现问题时，可以打印出整个path矩阵，检查每个节点对的中转节点是否正确。一个实用的调试方法是从小规模图（3-4个节点）开始验证。

3. 性能权衡 ：对于节点数超过500的图，Floyd算法可能不是最佳选择。在这种情况下，可以考虑：

   • 使用n次Dijkstra算法（使用优先队列优化）
   • 对于特定问题，可能有更优化的算法

4. 动态图的处理 ：如果图结构会动态变化（边权重频繁修改），可以考虑：

   • 增量式更新算法
   • 或者在某些情况下直接重新计算

// 动态图更新示例
public void updateEdge(int[][] dist, int u, int v, int newWeight) {
    if (dist[u][v] <= newWeight) return;
    
    dist[u][v] = newWeight;
    dist[v][u] = newWeight; // 无向图
    
    int n = dist.length;
    // 局部更新受影响的路径
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][u] + dist[u][v] + dist[v][j] < dist[i][j]) {
                dist[i][j] = dist[i][u] + dist[u][v] + dist[v][j];
            }
        }
    }
}

Floyd算法虽然理论简单，但在实际应用中却能解决许多复杂的路径规划问题。掌握它不仅有助于算法面试，更能为实际工程问题提供简洁有效的解决方案。