2
$\begingroup$

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                ​

$\endgroup$
2
$\begingroup$

This is indeed a correct approach.

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)


As a side note, if you prefer using non matrix-based algorithms, then you can use BFS which will work in linear time

$\endgroup$
1
$\begingroup$

Use the Floyd-Warshall algorithm, it was designed for exactly this kind of task.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.