1

I have to find the distances in a graph through the multiplication of a 2D array, and I am trying to multiply the array of the graph, it works but the output is not correct. And I don't know where the problem is!

public class Graph {
    private int[][] AdjacencyMatrix = {
            {0, 1, 0, 1, 0},
            {1, 0, 1, 0, 1},
            {0, 1, 0, 1, 0},
            {1, 0, 1, 0, 0},
            {0, 1, 0, 0, 0}};

    int size = AdjacencyMatrix.length;
    private int[][] distanceMatix = new int[size][size];

    public void multiply() {
        int sum = 0;
        //für alle Zeilen in this matrix
        for (int row = 0; row < size; row++) {
            //für alle Spalten in other matrix
            for (int col = 0; col < size; col++) {
                //this matrix -> für alle Zellen in der Zeile
                //other matrix -> für alle Zellen in der Spalte
                for (int index = 0; index < size; index++) {
                    if (row == col) {
                        distanceMatix[row][col] = 0;
                    } else {
                        distanceMatix[row][col] +=
                                AdjacencyMatrix[row][index] *
                                        AdjacencyMatrix[index][col];
                    }
                }
            }
        }

        System.out.println("\n-------- Print DistanceMatrix --------\n");
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(distanceMatix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

My Output:

0 0 2 0 1 
0 0 0 2 0 
2 0 0 0 1 
0 2 0 0 0 
1 0 1 0 0

The correct ouput is this:

0 1 2 1 2
1 0 1 2 1
2 1 0 1 2
1 2 1 0 3
2 1 2 3 0
Community
  • 1
  • 1
Reza Hosseini
  • 19
  • 4

2 Answers2

0

Your inner loop should look like this. Primitive arrays are intitialized to 0's upon creation and you don't want to skip an iteration when row == col.

for (int index = 0; index <  size; index++) {  
      distanceMatix[row][col] += AdjacencyMatrix[row][index] * 
                                 AdjacencyMatrix[index][col];
}

I used

1 2
3 4

And multiplied by hand and got

7 10
15 22

Which matches your program with above changes.

With regard to your expected answer, either it is wrong your input matrix may be wrong. You can verify your answers here

WJS
  • 36,363
  • 4
  • 24
  • 39
0

You can use a generic matrix multiplication approach so you don't get confused:

int size = 5;
int[][] matrix = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 0},
        {0, 1, 0, 0, 0}};

int[][] result = new int[size][size];
for (int row = 0; row < size; row++)
    for (int col = 0; col < size; col++)
        for (int index = 0; index < size; index++)
            result[row][col] += matrix[row][index] * matrix[index][col];

// output
for (int[] res : result) System.out.println(Arrays.toString(res));
//[2, 0, 2, 0, 1]
//[0, 3, 0, 2, 0]
//[2, 0, 2, 0, 1]
//[0, 2, 0, 2, 0]
//[1, 0, 1, 0, 1]

See also: An efficient way to multiply two object matrixes