弗洛伊德最短路径java

弗洛伊德最短路径算法（Floyd-Warshall algorithm）是一种用于求解图中所有节点之间最短路径的算法。它可以处理有向图或无向图，可以处理带有负权边的图，但不能处理带有负权环的图。

以下是弗洛伊德最短路径算法的Java实现：

public class FloydWarshall {
    private static final int INF = Integer.MAX_VALUE; // 代表无穷大的值

    public void shortestPath(int[][] graph) {
        int n = graph.length;

        int[][] dist = new int[n][n]; // 存储最短路径的距离

        // 初始化dist数组
        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][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 输出最短路径
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

使用该算法，你可以通过传入一个邻接矩阵表示的图来计算出图中所有节点之间的最短路径。其中，`graph`是一个二维数组，表示图的邻接矩阵，`graph[i][j]`表示节点i到节点j的距离。如果两个节点之间没有直接连接，则距离为无穷大（INF）。