Calculation of the path matrix from the adjacency matrix

Question

I am exploring a way to compute a path matrix from an adjacency matrix (say, AM1).

The path matrix of the graph G with n vertices is a Boolean n * n-matrix, the elements of which can be defined as:

p[i][j]=1(if there is a path from i to j) p[i][j]=0(otherwise) 

And the steps that I learned are as follows:

If we multiply the adjacency matrix A [] [] by ourselves, we get A ^ 2 (say, AM2), each vertex A [i] [j] basically represents the number of paths of length 2 from i to j.

Similarly, if we multiply the adjacency matrix 3 times, i.e. we get A ^ 3 (say, AM3), each vertex A [i] [j] basically represents the number of paths of path length 3 from i to j .. and so on.

Now we define a matrix X such that:

X = AM1 + AM2 + AM3 ... AMn (where n is the number of vertices)

From this X-matrix, we compute the path / reach capability matrix, replacing all nonzero vertices with 1.

What I cannot understand is how replacing all nonzero vertices with 1 gives us the path matrix. And why do we calculate or add the whole matrix to AMn.?.

I understand that X [i] [j] symbolizes the number of paths, the path length is n or less than n, from i to j, But why do we only calculate to n, no more or less?

Please explain!

Answer 1

What I can't understand is how replacing all nonzero vertices with 1 gives us the path matrix?

If A^k gives us the number of paths from i->j after steps k , a nonzero number means that the corresponding element in the path matrix must be true, since there is at least one path. Now this should be true for k=1 (cycles), k=2 , k=3 ... up to k=N ...

But why do we calculate only up to n, no more or less?

If there are only N vertices on the graph, there is a path from i->j , then the worst case is that there is a path that takes each intermediate vertex, i.e. N-1 steps, therefore, the calculation of A^N necessary.

Note that there are other, less expensive ways to compute the so-called path matrix. Essentially (for non-oriented graphs) you are looking for related components of a graph that can be run in linear time with a depth search. To calculate all A^k , each multiplication will require approximately O(N^3) time, N times for everything about O(N^4) . This can be avoided by diagonalizing the matrix O(N^3) , the eigenvalues ​​and eigenvectors give some idea of ​​the structure of the graph (much more than the path matrix itself!).