Floyd-Warshall algorithm implementation with list of lists

I want to use the Floyd-Warshall algorithm to find the shortest path between two vertices. The matrix is in an ArrayList<ArrayList<Integer>>. It is always fairly small, such as a 4x4 or 8x8 matrix.

In my class, I have a distance matrix already. I'm just trying to create the "shortest path" matrix. But it doesn't work. It fills my matrix wrong.

I really hope someone can look at this and explain what's wrong.

My distance matrix is:

 0   0  256 411
556  0  558  0
250  0   0  431
 0   0  431  0

Test output is:

 0   0   0   0 
556 556 556 556 
250 250 250 250 
 0   0   0   0

Expected:

500 0 842 681
556 0 806 967
 0  0 500 681
581 0  0  862

I've commented out my test output. distance is my matrix with the integer value of the distances between the vertices. In my matrix, i is y and j is x.

public ArrayList<ArrayList<Integer>> calcShortest() {
        //String test = "";
        ArrayList<ArrayList<Integer>> shortest = distance;

        for (int k = 0; k < airports.size(); k++) {
            for (int i = 0; i < airports.size(); i++) {
                for (int j = 0; j < airports.size(); j++) {
                    shortest.get(j).add(i, Math.min(shortest.get(k).get(i) + shortest.get(j).get(k), 
                            shortest.get(j).get(i)));
                }
            }
        }
        /*for (int j = 0; j < airports.size(); j++) {
            for (int i = 0; i < airports.size(); i++) {
                test += shortest.get(j).get(i) + " ";
            }
            System.out.println(test);
            test = "";
        }*/
        return shortest;
    }

Solution

There are a number of problems with your code and your data.

The add operation shortest.get(j).add(i, ...) inserts an element into the ArrayList. You actually want to set a value: shortest.get(j).set(i, ...)
The array indices are wrong. You're trying to do shortest[j][i] = min(shortest[k][i] + shortest[j][k], shortest[j][i]), but Floyd-Warshall calls for shortest[i][j] = min(shortest[i][k] + shortest[k][j], shortest[i][j]).
Your expected output doesn't make sense. How is it possible for shortest[2][2] to be 500? We already know that it's 0. And how do you figure that shortest[3][0] is 581? There is no way to get 581 from the distance matrix that you've given.
In the distance matrix, why do you have zero values off the diagonal? For example, distance[1][3] is 0. So the distance from node 1 to node 3 is 0? Really?
Why are you making shortest refer to distance? Since you're modifying distance, why not just use distance instead of pretending that you have a different matrix called shortest? Or did you intend to make a copy of distance?

The code below runs Floyd-Warshall correctly because it calls set to modify the ArrayList and it uses the correct indices. However, it does not produce what you call the "expected" result for your distance matrix because, as I have explained, your expected result doesn't make sense and the distance matrix itself is suspect.

  int n = shortest.size();
  for (int k = 0; k < n; k++) { 
    for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
        shortest.get(i).set(j,
            Math.min(shortest.get(i).get(k) + shortest.get(k).get(j), 
                     shortest.get(i).get(j)));
      } 
    } 
  }