Finding all possible paths in graph with matrix

468 Views Asked by At

Let's assume we have a one-direction graph and we want to produce a matrix that represents relations:

the structure of graph image

At first step we have only a matrix that contains straight relations, so for given image we have this matrix:

    A    B    C    D    E    F    G

A   1    1    1    0    0    0    0

B   0    1    0    1    0    0    0

C   0    0    1    0    1    1    0

D   0    0    0    1    0    0    0

E   0    0    0    0    1    0    0

F   0    0    0    0    0    1    1

G   0    0    0    0    0    0    1

Now I want a way to calculate final matrix in a way that for each node, if there is any path to destination node, it has 1 else 0 in the matrix:

    A    B    C    D    E    F    G

A   1    1    1    1    1    1    1

B   0    1    0    1    0    0    0

C   0    0    1    0    1    1    1

D   0    0    0    1    0    0    0

E   0    0    0    0    1    0    0

F   0    0    0    0    0    1    1

G   0    0    0    0    0    0    1

If we call the first matrix A, what should I do to achieve the second matrix?

1

There are 1 best solutions below

1
On BEST ANSWER

I found that if we calculate A^n (where n is the number of nodes), we find a new matrix that has some 0 values and some positive ones. If we replace each positive number with 1, the final matrix will be produced.