What is wrong with my Floyd Warshall algorithm?

Question

Here is the problem link

Approach:

My approach is to simply give every other node the chance to be an in-between node for every 2 pairs of vertices i and j.

Below is my code for Floyd Warshall algorithm:

class Solution{
    public void shortest_distance(int[][] mat){
        int N = mat.length;
        
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++ j){
                for(int k = 0; k < N; ++k){
                    if(mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j])){
                        mat[i][j] = mat[i][k] + mat[k][j];
                    }
                }
            }
        }
    }
}

This gives wrong answer for the below case:

Input

12
0 4 2 1 2 9 4 8 -1 4 -1 -1
9 0 3 6 2 6 2 3 6 -1 -1 3
7 1 0 10 8 9 1 3 -1 7 -1 10
5 1 9 0 3 -1 1 10 7 1 -1 7
-1 5 1 4 0 2 10 4 10 6 4 5
7 8 3 7 5 0 5 1 3 5 7 2
6 -1 6 1 10 7 0 10 -1 -1 7 7
-1 3 2 7 4 -1 4 0 10 5 6 10
10 6 1 10 4 4 7 10 0 4 7 4
1 1 6 8 8 9 2 10 6 0 -1 3
5 9 3 -1 4 3 -1 -1 -1 3 0 1
2 2 8 6 2 4 4 3 -1 3 4 0

My output

0 2 2 1 2 4 2 5 7 2 6 5
5 0 3 3 2 4 2 3 6 4 6 3
6 1 0 2 3 5 1 3 7 3 7 4
2 1 4 0 3 5 1 4 7 1 7 4
6 2 1 3 0 2 2 3 5 4 4 4
4 4 3 5 4 0 4 1 3 5 6 2
3 2 5 1 4 6 0 5 8 2 7 5
6 3 2 4 4 6 3 0 9 5 6 6
5 2 1 3 4 4 2 4 0 4 7 4
1 1 3 2 3 5 2 4 6 0 7 3
3 3 3 4 3 3 4 4 6 3 0 1
2 2 3 3 2 4 4 3 7 3 4 0

Expected Output

0 2 2 1 2 4 2 5 7 2 6 5
5 0 3 3 2 4 2 3 6 4 6 3
4 1 0 2 3 5 1 3 7 3 7 4
2 1 4 0 3 5 1 4 7 1 7 4
5 2 1 3 0 2 2 3 5 4 4 4
4 4 3 5 4 0 4 1 3 5 6 2
3 2 5 1 4 6 0 5 8 2 7 5
6 3 2 4 4 6 3 0 9 5 6 6
5 2 1 3 4 4 2 4 0 4 7 4
1 1 3 2 3 5 2 4 6 0 7 3
3 3 3 4 3 3 4 4 6 3 0 1
2 2 3 3 2 4 4 3 7 3 4 0

Note: I have also observed that if I move the k loop out and make it the first loop, it works just fine. I am confused as to what is wrong with my current code.

Answer 1

It is all about states. This is more conceptual than any algorithmic implementation issue here.

As in your code,

for(i...)
 for(j..)
  for(k...)
    mat[i][j] = mat[i][k] + mat[k][j];

The above states, for every pair of nodes i and j, check if any shortest path exists via every possible k. However, you are implicitly assuming that mat[i][k] and mat[k][j] are in already optimized states. This is incorrect as there is no real effort made in the code to bring them to that state.

---

Instead, you need to check for every pair of nodes i and j via only 1 value of k at a time. This is how you would be building the optimized states for every possible k one by one and the next one depending on the previous one. Hence, the below is correct version for this:

class Solution{
    public void shortest_distance(int[][] mat){
        int N = mat.length;
        for(int k = 0; k < N; ++k){
            for(int i = 0; i < N; ++i){
                for(int j = 0; j < N; ++j){
                    if(mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j])){
                        mat[i][j] = mat[i][k] + mat[k][j];
                    }
                }
            }
        }
    }
}

Quoting from the Wiki.

The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with {\displaystyle \Theta (|V|^{3})}\Theta (|V|^{3}) comparisons in a graph, even though there may be up to {\displaystyle \Omega (|V|^{2})}{\displaystyle \Omega (|V|^{2})} edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.

---

Miscellaneous:

Although trivial, but I still think it is worth mentioning that the order of nodes used in the optimization process really doesn't matter. We simply need to shorten the distance(if exists and possible) node by node where every node is an intermediate candidate.

class Solution{
    public void shortest_distance(int[][] mat){
        int N = mat.length;
        List<Integer> nodes = new ArrayList<>();
        for(int i = 0; i < N; ++i) nodes.add(i);
        Collections.shuffle(nodes);
        
        for(int l = 0; l < nodes.size(); ++l){
            int k = nodes.get(l);
            for(int i = 0; i < N; ++i){
                for(int j = 0; j < N; ++j){
                    if(mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j])){
                        mat[i][j] = mat[i][k] + mat[k][j];
                    }
                }
            }
        }
    }
}