简单的 Floyd-Warshall 算法 Java 实现似乎无法正常工作？

Question

简单的 Floyd-Warshall 算法 Java 实现似乎无法正常工作？

4

我一直在尝试在Java中实现Floyd-Warshall算法，而不使用“三个嵌套的for循环”的方式，但是我似乎无法弄清楚代码哪里出了问题。

这是显示我的顶点如何连接的地图。白色数字是顶点，黑色数字是连接顶点之间的距离。

顶点地图：http://i.imgur.com/htcaA4y.png 运行迭代后，我得到了以下最终的距离和序列矩阵。在最终序列矩阵（右侧的矩阵）上标有“something's wrong”的那一栏。为了从任何其他顶点到达顶点8，路径必须首先从顶点8到9，然后到10（但根据矩阵情况，它直接从顶点8到10）。

输出矩阵：http://i.imgur.com/o6fQweH.png 这是代码。有什么问题吗？

import java.util.ArrayList;

public class Main_Simple {

    public static void main(String[] args) {

        // 1. Setup the distance matrix
        //  -inf for vertices that are not connected
        //  -### for edge weights of vertices that are connected
        //  -0 across the diagonal

        int inf = 1000000; // Temporary 'infinity' variable

        // Initial distance matrix must be n x n
        int[][] initialDistanceMatrix = {
                {0, 1,  inf,    1,  inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf},
                {1, 0,  1,  inf,    1,  inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf},
                {inf,   1,  0,  inf,    inf,    1,  inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf},
                {1, inf,    inf,    0,  1,  inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf},
                {inf,   1,  inf,    1,  0,  1,  inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf},
                {inf,   inf,    1,  inf,    1,  0,  2,  inf,    inf,    1,  inf,    inf,    inf,    inf,    inf},
                {inf,   inf,    inf,    inf,    inf,    2,  0,  inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    0,  1,  inf,    inf,    inf,    inf,    inf,    inf},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    1,  0,  1,  inf,    inf,    inf,    inf,    inf},
                {inf,   inf,    inf,    inf,    inf,    1,  inf,    inf,    1,  0,  2,  1,  inf,    inf,    inf},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    2,  0,  inf,    inf,    inf,    2},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    1,  inf,    0,  1,  inf,    inf},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    1,  0,  1,  inf},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    1,  0,  1},
                {inf,   inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    inf,    2,  inf,    inf,    1,  0}
        };

        // 2. Setup the sequence matrix
        //  -All of column-1 are ones
        //  -All of column-2 are twos
        //  -etc
        //  -0 across the diagonal

        // Initial sequence matrix must be the same size as the initial distance matrix
        int[][] initialSequenceMatrix = new int[initialDistanceMatrix.length][initialDistanceMatrix.length];
        for (int row = 0; row < initialSequenceMatrix.length; row++) {
            for (int column = 0; column < initialSequenceMatrix.length; column++) {
                if (row == column) {
                    initialSequenceMatrix[row][column] = 0;
                } else {
                    initialSequenceMatrix[row][column] = column + 1; // +1 to account 0-based array
                }
            }
        }

        // 3. Iterate through the matrices (n-1) times
        //  -On the kth iteration, copy the kth column and kth row down to the next distance and sequence matrix
        //  -On the kth iteration, check matrix (k-1) and take the minimum of the following two:
        //      -d(ij)
        //      -d(ik)+d(kj)
        //      where i = row number, j = column number, and k = iteration number
        //  -After the distance matrix has been calculated, compare the current distance matrix to the previous.
        //  If the numbers are the same, keep the sequence matrix the same.  Otherwise, change the sequence
        //  matrix to the current iteration's number.

        ArrayList<int[][]> distanceMatrices = new ArrayList<int[][]>();
        distanceMatrices.add(initialDistanceMatrix);

        ArrayList<int[][]> sequenceMatrices = new ArrayList<int[][]>();
        sequenceMatrices.add(initialSequenceMatrix);

        // Print the matrices to make sure they are made correctly
        printMatrix(initialDistanceMatrix, "Initial distance matrix");
        printMatrix(initialSequenceMatrix, "Initial sequence matrix");

        // Matrix Iteration Loops
        for (int iteration = 1; iteration < initialDistanceMatrix.length; iteration++) {

            // Initialize new distance matrix
            int[][] currentDistanceMatrix = new int[initialDistanceMatrix.length][initialDistanceMatrix.length];
            for (int row = 0; row < currentDistanceMatrix.length; row++) {
                for (int column = 0; column < currentDistanceMatrix.length; column++) {
                    currentDistanceMatrix[row][column] = 0;
                } // ends 'column' loop
            } // ends 'row' loop

            // Distance Matrix iteration
            for (int row = 0; row < currentDistanceMatrix.length; row++) {
                for (int column = 0; column < currentDistanceMatrix.length; column++) {

                    if (row == column) { // If you are on the diagonal, insert '0'
                        currentDistanceMatrix[row][column] = 0;
                    } else if (row == (iteration - 1) || column == (iteration - 1)) { // Brings down the row and column of the iteration (-1 to account 0-based array)
                        currentDistanceMatrix[row][column] = distanceMatrices.get(iteration - 1)[row][column];
                    } else { // If you are on any other square...
                        int Dij = distanceMatrices.get(iteration - 1)[row][column];
                        int Dik_Dkj = distanceMatrices.get(iteration - 1)[row][iteration - 1] + distanceMatrices.get(iteration - 1)[iteration - 1][column];

                        if (Dij > Dik_Dkj) currentDistanceMatrix[row][column] = Dik_Dkj;
                        else currentDistanceMatrix[row][column] = Dij;
                    }

                } // ends 'column' loop
            } // ends 'row' loop

            // Add the distance matrix to the matrix array
            distanceMatrices.add(currentDistanceMatrix);

            // Initialize new sequence matrix
            int[][] currentSequenceMatrix = new int[initialDistanceMatrix.length][initialDistanceMatrix.length];

            // Sequence Matrix iteration
            for (int row = 0; row < currentSequenceMatrix.length; row++) {
                for (int column = 0; column < currentSequenceMatrix.length; column++) {

                    if (row == column) { // If you are along the diagonal...
                        currentSequenceMatrix[row][column] = 0;
                    } else if (row == (iteration - 1) || column == (iteration - 1)) { // If you are on the same row or column as the iteration...
                        currentSequenceMatrix[row][column] = sequenceMatrices.get(iteration - 1)[row][column];
                    } else { // If you are on any other square...
                        // You need to check the current distance matrix to see if it matches the previous.
                        // If it does match, keep the same number.
                        // If it changed, changed the number in that cell to the current iteration

                        // Compare the most recent distance matrix to the one before it
                        if (distanceMatrices.get(distanceMatrices.size() - 1)[row][column] == distanceMatrices.get(distanceMatrices.size() - 2)[row][column]) {
                            currentSequenceMatrix[row][column] = sequenceMatrices.get(sequenceMatrices.size() - 1)[row][column];
                        } else {
                            currentSequenceMatrix[row][column] = iteration;
                        }
                    }

                } // ends 'column' loop
            } // ends 'row' loop

            // Add the sequence matrix to the matrix array
            sequenceMatrices.add(currentSequenceMatrix);

        } // ends matrix iteration loops

        System.out.println("-------------------------------------------------------");

        printMatrix(distanceMatrices.get(distanceMatrices.size() - 1), "Final Distance Matrix");
        printMatrix(sequenceMatrices.get(sequenceMatrices.size() - 1), "Final Sequence Matrix");

    } // ends main method

    public static void printMatrix(int[][] matrix, String message) {
        System.out.println("\n" + message);
        for (int row = 0; row < matrix.length; row++) {
            for (int column = 0; column < matrix.length; column++) {
                System.out.print(matrix[row][column] + "\t");
            } // ends 'column' loop
            System.out.println();
        } // ends 'row' loop
        System.out.println();
    }

} // ends class Main_Simple

- ngserdna

2

你尝试过使用一个小得多的地图来调试你的实现吗？ - user824425

@Rhymoid 是的，它似乎在5x5、6x6和7x7矩阵上运行良好。很奇怪为什么它在这张地图上根本不起作用。也许我对 Floyd-W 算法缺少一些基本的了解？ - ngserdna

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AndyN · Answer 1

在第一次循环中，您没有正确地遍历所有顶点。

for (int iteration = 1; iteration < initialDistanceMatrix.length; iteration++)

应该是：

for (int iteration = 1; iteration < initialDistanceMatrix.length + 1; iteration++)

或者，更好的方法是，不要使用iteration - 1作为所有数组索引的值，而是使用iteration，这样你就可以使用：

for (int iteration = 0; iteration < initialDistanceMatrix.length; iteration++)

这样可以保持所有索引从零开始，而不是混合使用。我只通过这个代码更改（和一个较小的测试用例）就得到了正确的答案。