Simple Floyd-Warshall算法Java實現似乎不工作？

Question

我一直試圖在Java中實現Floyd-Warshall算法，但沒有使用「三for-loop-nested」方法，但我似乎無法弄清楚我在代碼中出錯的地方。

這是顯示我的頂點如何連接的地圖。白色數字是頂點，黑色數字是連接頂點之間的距離。

地圖頂點：http://i.imgur.com/htcaA4y.png

正在運行的迭代之後，我得到下面的最終距離和序列矩陣。說「有問題」的東西是最後一個序列矩陣（右邊一列）的第8列。爲了從任何其他頂點到達頂點8，路徑必須首先從頂點8到9，然後從THEN到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 

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++) 

這保持您的所有索引爲零而不是混合它們。我只用這個代碼更改（和一個更小的測試用例）就得到了正確的答案。