MATLAB: Finding a chain in an adjacency matrix

MATLABmatrixmatrix manipulationneural networks

Hi everyone,
I have a binary matrix A representing edges in a graph, of size n x m. It is easy to know if elements i and j are connected by an edge: I simply look up if A(i,j)==1. However, I want to know if there is a chain of size k (or smaller) that connects i and j. For example, A(i,k)==1 and A(k,j)==1. Any ideas or maybe a pre-existing function that I have not found?
I have no interest whatsoever in finding the shortest path, I just care if there is any. Thanks

Best Answer

T = eye(size(A)) ;
found = false;
for n = 0 : k -  1
  if T(i, j)
    found = true;
    break;
  end
  T = T * A;
end
chain_exists = found | T(i, j);
Related Question