Computation of Path Matrix from the adjacency Matrix
adjacency-matrix, graph
Solution
What i am unable to grasp is how does replacing all non-zero vertices by 1 gives us the path matrix?
If `A^k` gives us the number of paths from `i->j` after `k` steps, a non-zero number means that the corresponding entry in the path matrix should be True, since at least one path exists. Now this must be true for `k=1` (loops), `k=2`, `k=3`... all the way to `k=N`...
But why do we calculate only until n,not more or less?
If there is a path from `i->j` on a graph with only N vertices, the worst case is that there is a path that takes every intermediate vertex, i.e. N-1 steps, hence the need for the calculation of `A^N`.
Note that there are other, less expensive ways to calculate the so-called path matrix. Essentially (for undirected graphs), you are looking for the connected components of the graph, which can be done in linear time with a depth-first search. To calculate all the `A^k` each multiplication would require approximately `O(N^3)` time, `N` times for a total of about `O(N^4)`. This can be avoided with a a diagonalization of the matrix, `O(N^3)`, whose eigenvalues and eigenvectors give some insight to the structure of the graph (far more than the path matrix itself!).
Problem
I am learning the way of computing Path Matrix from Adjacency Matrix(say AM1). A Path Matrix of a graph G with n vertices is a Boolean n*n matrix whose elements 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 i learned is as follows: If we multiply an adjacency matrix A[][] by itself we get A^2(say AM2) whose each vertex A[i][j] basically represents the number of paths of path length 2 from i to j. Similarly,If we multiply an adjacency matrix 3 times i.e we get A^3(say AM3) whose 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 ability matrix by replacing all non-zero vertices by 1. What i am unable to grasp is how does replacing all non-zero vertices by 1 gives us the path matrix.?. And why we calculate or add all the matrix up to AMn.?. I understand that X[i][j] symbolizes number of paths, of path length n or less than n,from i to j,But why do we calculate only until n,not more or less? Please explain!