The simple java implementation of the Floyd warhall algorithm doesn’t seem to work?
I have been trying to implement Floyd warhall algorithm in Java instead of "three loop nesting", but I can't seem to figure out where I made mistakes in the code
This is a map showing how my vertices are connected White numbers are vertices and black numbers are the distance between connected vertices
Vertex map: http://i.imgur.com/htcaA4y.png
After running the iteration, I get the following final distance and sequence matrix What says "wrong" is column 8 of the final sequence matrix (the one on the right) In order to reach vertex 8 from any other vertex, the path must first change from vertex 8 to 9 and then to 10 (according to the matrix, this is not the case – it changes directly from vertex 8 to 10)
Output matrix: http://i.imgur.com/o6fQweH.png
This is the code What seems to be the problem?
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,inf},{1,{inf,2,2},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
Solution
You did not iterate all vertices correctly on the first loop
for (int iteration = 1; iteration < initialDistanceMatrix.length; iteration++)
should:
for (int iteration = 1; iteration < initialDistanceMatrix.length + 1; iteration++)
Or, better yet, instead of using iteration – 1 to index all arrays, use iteration, and then you can use:
for (int iteration = 0; iteration < initialDistanceMatrix.length; iteration++)
This keeps all indexes zero instead of mixing them Only this code change (and smaller test cases) did I get the right answer