# Algorithm to find all paths of length k

Consider the following definition of 3-friends:

person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or person 1 is friends with a friend of a friend of person 2.

In graph-theoretical terms, person 1 is a 3-friend with another person 2 if there is a path of length 1, 2 or 3 from vertex 1 to vertex 2.

Is there an efficient algorithm to find all the paths between say person 1 and all its 3-friends? (I.e. all the paths of length 3, all the paths of length 2, all the paths of length 1).

Or the only option is an exhaustive search?

• Do you want all the paths or just all the $k$-friends? Or a path to each friend (but not necessarily all of the paths to a given friend)? May 26, 2015 at 14:08
• @Tom van der Zanden All the k friends can probably be computed with a variation of Dijkstra's which might also give a shortest path to them. I am interested in all paths but would say finding all shortest paths be faster? May 26, 2015 at 14:17

You are asking for all paths of length 3 emanating from a given vertex. There are $O(n^3)$ of these, the worst case being a clique. If you want to actually output all of them, then exhaustive search (on the adjacency matrix) is the perfect algorithm, and it is efficient, since there are only $O(n^3)$ paths (or less).