# Algorithm that will find the minimum number of steps to get from state $j$ to state $i$

Consider an adjacency matrix $$A$$ with elements $$[A]_{ij}=1$$ if one can reach state $$i$$ from state $$j$$ in one timestep, and $$0$$ otherwise. The matrix $$[A^k]_{ij}$$ represents the number of paths that lead from state $$j$$ to $$i$$ in $$k$$ timesteps. Derive an algorithm that will find the minimum number of step to get from state $$j$$ to state $$i$$.

Here is my attempt:

The algorithm takes as input:

• $$A$$ - Adjacency matrix
• $$j$$ and $$i$$ - the vertices for which we want to find the minimum path inbetween

Then it calculates in a while loop for which value of $$k$$, $$[A^k]_{ij}\neq 0$$ and returns that value of $$k$$. This way we get the minimum value of $$k$$ for which there exists a path.

Here is the pseudocode:

(Is this the correct way to do it and would there be a faster way?)

shortestPath(A,j,i):
if [A]_{ij}=1:
return 1
else:
f=0; k=1
while f=0:
f = [A^k]_{ij}
k = k + 1
return k                ​


It can be improved further by using binary search on $$k$$, but you have to be careful with it since you want to multiply a small number of matrices (and computing $$A^r$$ for an arbitrary $$r$$, can take a lot of time using a simple multiplication algorithm)