简单的Floyd-Warshall算法Java实现似乎不起作用?
发布时间:2020-12-15 02:11:19 所属栏目:Java 来源:网络整理
导读:我一直在尝试用 Java实现Floyd-Warshall算法而不使用“三循环嵌套”方式,但我似乎无法弄清楚我在代码中出错的地方. 这是显示我的顶点如何连接的地图.白色数字是顶点,黑色数字是连接顶点之间的距离. 顶点地图:http://i.imgur.com/htcaA4y.png 运行迭代后,我
我一直在尝试用
Java实现Floyd-Warshall算法而不使用“三循环嵌套”方式,但我似乎无法弄清楚我在代码中出错的地方.
这是显示我的顶点如何连接的地图.白色数字是顶点,黑色数字是连接顶点之间的距离. 顶点地图:http://i.imgur.com/htcaA4y.png 运行迭代后,我得到以下最终距离和序列矩阵.说“出错了”的是最终序列矩阵的第8列(右边的那个).为了从任何其他顶点到达顶点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,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 解决方法
您没有在第一个循环上正确迭代所有顶点.
for (int iteration = 1; iteration < initialDistanceMatrix.length; iteration++) 应该: for (int iteration = 1; iteration < initialDistanceMatrix.length + 1; iteration++) 或者,更好的是,不是使用迭代 – 1为所有数组索引,使用迭代,然后您可以使用: for (int iteration = 0; iteration < initialDistanceMatrix.length; iteration++) 这样可以使所有索引保持零,而不是混合它们.只有这个代码更改(以及更小的测试用例)我得到了正确的答案. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |