当前位置： 首页 > news >正文

从邻接矩阵到路径还原：一个完整的Floyd算法Java实战项目（附LeetCode刷题指南）

news 2026/6/13 10:07:59

从邻接矩阵到路径还原：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题目：

    1. Network Delay Time
    1. Course Schedule IV
    1. 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算法虽然理论简单，但在实际应用中却能解决许多复杂的路径规划问题。掌握它不仅有助于算法面试，更能为实际工程问题提供简洁有效的解决方案。

http://www.rkmt.cn/news/1432266.html

相关文章：

  • ESP32开发板到手别吃灰！5分钟用VSCode和PlatformIO跑通你的第一个物联网程序
  • [智能体-166]：Langchain有哪些结构化地方和对应的方法？代码示例
  • 保姆级教程：用Unity UGUI与World Space Canvas搞定3D游戏中的动态血条与摇杆控制
  • GRBL算法调参避坑指南：如何根据你的步进电机和机械结构优化STM32运动性能
  • VASP过渡态计算避坑指南：CI-NEB方法中INCAR参数设置与收敛性诊断实战
  • 手把手调优：如何榨干寒武纪MLU的算力？从Cluster到Core的并发与流水线实战
  • 新手别慌！一文拆解SMIC 180nm工艺库里的那些文件夹都是干啥的
  • 别再傻傻分不清！TVS管选型必懂的三个电压：VRWM、VBR、VCL实战解析
  • 从调度脚本到自主决策，AI-ETL整合全路径拆解，手把手落地4类高危场景改造方案
  • 低成本语音AI实战：本地部署TTS与大模型集成方案
  • AI搜索隐私保卫战进入倒计时：监管新规落地前最后窗口期，如何用3个命令行工具实时监控自身数据流向？
  • AI如何重塑数字营销：从个性化推荐到人机协同创意
  • 手把手教你用高云FPGA的Video Frame Buffer IP核搞定OV5640摄像头到HDMI显示（附源码）
  • 企业规模化应用AI的五大成熟度信号与实施路线图
  • AI重塑师生关系：从工具到伙伴的动态三角模型与实操策略
  • ImageJ进阶玩法：用Trainable Weka Segmentation，让机器学习帮你自动数免疫组化的阳性细胞
  • 从弹珠游戏到工业分选：Rocky DEM模拟揭示的颗粒动力学秘密（附高尔顿板案例文件）
  • AI工具供应商尽职调查全流程（含12份法律条款审查红标模板）
  • 怎样高效自动化下载Google Drive共享文件：Python开发者的终极实践指南
  • 从2017年语音AI预测复盘看技术落地：场景、混合智能与实战方法论
  • 径向基函数(RBF)插值：从数学原理到工程实战的完整指南
  • 明末：渊虚之羽下载2026最新
  • 别再死记硬背了！用‘温室控制器’和‘牙科诊所’两个例子，彻底搞懂面向对象分析的三大模型
  • 告别动画师地狱：用UE5 IK重定向器，5分钟让不同骨架的角色共享一套动作库
  • 构建高效技术阅读系统：从信息过载到知识沉淀的实践指南
  • 传统对讲在工业噪声下形同虚设？A-59P用AI降噪+8米拾音交出满分答卷
  • MediaPipe姿势捕捉实战：结合Pygame，教你开发一个体感小游戏（附完整源码）
  • 语音助手安全漏洞剖析与多层防御实践指南
  • 游戏修改入门：用Cheat Engine 7.5搞定单双浮点数（附第三关详细图文）
  • 智慧建筑物分割图像识别 混凝土裂缝分割 房屋巡检识别 老旧房屋缺陷检测 yolo+voc+coco数据集第10732期