Transitive closure and Warshall algorithm

user_12462033 0
Viewed 160

My input matrix is following:

0 1 1 0
0 0 1 0
1 0 0 1
0 0 0 0

My code for the Warshall's algorithm is following:

int V = A.length;
     for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
           for(int j = 0; j < V; j++) {
              A[i][j] = A[i][j] == 1 || A[i][k] == 1 && A[k][j] == 1 ? 1 : 0;
           }
        }
     }

The formula for the transitive closure of a matrix is (matrix)^2 + (matrix). Following the formula, I get this as an answer:

1 1 1 1
1 0 1 1
1 1 1 1
0 0 0 0

Using the piece of code I mentioned before, i get this as an answer:

1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0

So, my question is following, which one of the answers is right and is the algorithm working the correct way?

algorithm java
1 Answers

The formula for the transitive closure of a matrix is (matrix)^2 + (matrix). Following the formula, I get this as an answer:

Not exactly, you are looking for the transitive closure of (matrix)^2 + matrix, this is the formula for a single step - not for the entire solution.

This means, you need to apply it again, and then you get in a second iteration:

1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0

(Since there is a path from 0 to 1)

The third iteration will apply the same matrix, which means this is the transitive closure.

So, from this test case, it seems the algorithm is corret.

That said, the line A[i][j] = A[i][j] == 1 || A[i][k] == 1 && A[k][j] == 1 ? 1 : 0; is quite unreadable, imho - don't be afraid to break it or at least add some parentheses

user_5726700
Related