# How to find the distance between two nodes in an undirected graph, from a neighborhood matrix?

Given a distance-1 neighborhood matrix representing an undirected graph, I'm trying to calculate the distances between two nodes so I can work out the distance-2 matrix, then the distance-3 matrix, and so on...

How to find this distance?

Any help would be appreciated.

• What do you mean by "distance-k matrix"? – xskxzr May 6 '18 at 14:21

## 1 Answer

I assume that by distance-$2$ matrix you mean the matrix $A$ such that $A_{ij}=1$ if there is a path of length exactly $2$ between node $i$ and node $j$.

Let us call $B$ the distance-$1$ matrix, then remember that $B^2$ is such that $(B^2)_{ij}$ is the number of paths of legth $2$ between $i$ and $j$. So all you have to do is to check whether an entry of $B^2$ is $0$ or not.

• Thanks, but given an adjacency matrix, how could I work out distance-3, distance-4, distance-5, etc? – Steve C. May 6 '18 at 11:44
• What I wrote works for arbitrary $n$s: if you consider $B^n$, $(B^n)_{ij}$ is the number of paths of length $n$ between $i$ and $j$. – Leo163 May 6 '18 at 11:52