Computation of Path Matrix from the adjacency Matrix

5
votes

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!

1
graphadjacency-matrix

1 Answers

3
votes

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