4
votes

I've been trying to implement the Floyd-Warshall Algorithm in Java without using the "three for-loop-nested" way, but I can't seem to figure out where I've gone wrong in the code.

This is the map that shows how my vertices are connected. The white numbers are the vertices, and the black numbers are the distances between connected vertices.

Map of Vertices: http://i.imgur.com/htcaA4y.png

After running the iterations, I get the following final Distance and Sequence Matrices. The thing that says "something's wrong" is column 8 on the final sequence matrix (the one on the right). In order to get to vertex 8 from any other vertex, the path must first go from vertex 8 to 9, and THEN to 10 (which isn't the case according to the matrix--it goes straight from vertex 8 to 10).

Output Matrix: http://i.imgur.com/o6fQweH.png

Here's the code. What seems to be the issue?


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
1
Have you tried to debug your implementation with a much, much smaller map? - user824425
@Rhymoid Yes, it seemed to work on a 5x5, 6x6, and 7x7 matrices. its weird how it simply doesn't work on this map. Maybe I'm missing something fundamental about the Floyd-W algorithm? - ngserdna

1 Answers

0
votes

You're not iterating through all of the vertices properly on the first loop.

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

Should be:

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

Or, better yet, instead of using iteration - 1 for all of your array indexes, use iteration, and then you can use:

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

This keeps all of your indexes zero based rather than mixing them. I got the correct answer with only this code change (and a smaller test case).