CODEWITHSUNDEEP
javaalgorithm
Captain n00b
Captain n00b

Reputation: 63

What am I missing in my Warshall algorithm?

I am trying to implement Warshall's algorithm to find the transitive closure of an adjacency matrix. This is what I have for the function:

public static int[][] warshall(int A[][]){
    int R[][] = A;
    for (int k = 1; k < n; k++) {
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if ((R[i][j] == 1) || ((R[i][k] == 1) && (R[k][j] == 1))) {
                    A[i][j] = 1;
                }
            }
        }
        R = A.clone();
    }
    return A;
}

I'm using the following adjacency matrix to test:

0100
0001
0000
1010

Which should result in :

1111
1111
0000
1111

I'm not getting anywhere close to this. Can anyone readily see what I am missing?

Thanks for any tips or suggestions.

Upvotes: 1

Views: 53

Answers (1)

Eric
Eric

Reputation: 19873

I am not familiar with this particular algorithm but in Java and many other languages (most of them actually), you should ALWAYS start your for loops with index at 0 and NOT 1.

Upvotes: 2

Related Questions