Java实现最短路径的动态规划方法（小白也能看懂的Java最短路径DP教程）

Floyd-Warshall 算法：多源最短路径的DP解法

虽然Dijkstra算法适用于单源最短路径，但当我们需要计算图中所有顶点对之间的最短路径时，Floyd-Warshall算法是一个经典的动态规划解决方案。

该算法的时间复杂度为 O(n³)，空间复杂度为 O(n²)，非常适合稠密图或需要全源最短路径的场景。

算法思路

• 设 dist[i][j] 表示从顶点 i 到顶点 j 的最短距离。
• 初始时，dist[i][j] 为直接边的权重（若无边则为无穷大）。
• 对于每一个中间顶点 k，尝试通过 k 来缩短 i 到 j 的路径： dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Java代码实现

public class FloydWarshall {    private static final int INF = 99999; // 表示无穷大    public static void floydWarshall(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];            }        }        // 动态规划核心：枚举中间点 k        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][k] + dist[k][j] < dist[i][j]) {                        dist[i][j] = dist[i][k] + dist[k][j];                    }                }            }        }        // 打印结果        printSolution(dist);    }    private static void printSolution(int[][] dist) {        System.out.println("最短路径距离矩阵：");        for (int i = 0; i < dist.length; i++) {            for (int j = 0; j < dist.length; j++) {                if (dist[i][j] == INF)                    System.out.printf("%7s", "INF");                else                    System.out.printf("%7d", dist[i][j]);            }            System.out.println();        }    }    public static void main(String[] args) {        // 示例图：4个顶点        int[][] graph = {            {0, 3, INF, 7},            {8, 0, 2, INF},            {5, INF, 0, 1},            {2, INF, INF, 0}        };        floydWarshall(graph);    }}

运行结果说明

上述代码将输出一个 4x4 的矩阵，表示任意两个顶点之间的最短距离。例如，dist[0][2] 表示从顶点 0 到顶点 2 的最短路径长度。

为什么选择动态规划？

相比暴力搜索，动态规划通过记忆化避免了重复计算，大大提升了效率。对于图论最短路径Java实现来说，Floyd-Warshall 是理解 DP 思想的绝佳入门案例。

总结

通过本教程，你已经掌握了：

• 动态规划在最短路径问题中的应用原理
• Floyd-Warshall 算法的 Java 实现
• 如何阅读和调试最短路径结果

现在，你可以尝试修改图的结构，或者将算法封装成工具类，用于你的项目中！记住，Java最短路径算法不仅是面试高频题，更是实际开发中的实用技能。

继续练习，你离成为算法高手又近了一步！