弗洛伊德算法java

弗洛伊德（Floyd-Warshall）算法是一种用于求解图中最短路径的动态规划方法。它可以在有向或无向、加权或非加权图中找到任意两点之间的最短路径。在Java中实现弗洛伊德算法，通常涉及以下几个步骤：

1. 初始化一个二维数组，其中`dist[i][j]`表示从节点i到节点j的最短路径长度，默认值为无穷大，除了对角线元素（即i=j时），初始值为0，因为每个节点到自身的距离总是0。

2. 使用三层嵌套循环，对于图中的每一个节点k，更新所有节点对(i, j)之间的最短路径，如果通过节点k可以得到更短的距离，就更新`dist[i][j]`。

3. 循环次数等于节点数的平方，每次迭代都能发现新的最短路径。

以下是简单的Java代码实现示例：

public class FloydWarshall {
    private int[][] graph;

    public FloydWarshall(int[][] matrix) {
        this.graph = matrix;
    }

    public void floydWarshall() {
        int n = graph.length;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    // 返回矩阵表示的最短路径
    public int[] getShortestPaths(int src) {
        return Arrays.copyOfRange(graph[src], 1, n);
    }
}