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!).