Fixed length path between two graph nodes.

Question

Is there an algorithm that will, if given two nodes on a graph, find a route between them that takes the specified number of hops? Any node can be connected to any other.

The points at the moment are located in 2D space, so I'm not sure if a graph is the best approach.

Answer 1

If you have nodes are seeking to find routes in terms of hops, then a graph is probably the right approach. I'm not sure I understand what you are trying to do and what the constraints are, though, especially with respect to "Any Node can be connected to any other" .. which seems a bit open ended.

Disregarding that, however; with some graph representation:

It seems like starting at the first node, and doing a depth first search from there, and terminating a search if (a) the hops taken is larger than your specified number or (b) we have arrived at the second node; this will determine the first (not only) path connecting the two nodes in (at most) that many hops.

If it has to be exactly the specified hops, terminate any branch of the search if the hops have gone over, and terminate with success if you have also arrived at the second node.

Answer 2

Have you tried iterated-deepening DFS?

Answer 3

Dumb approach: (data structure is array of stacks). This is basically doing Breadth First Search (BFS) to depth N, except that if loops are allowed (you did not clarify but I assume they are), you don't exclude the visited nodes from further searching.

1. Push starting node on a stack stored in the array at index 0 (index=depth)

2. For each level/index "l" 0-N:

   For each node on a stack stored at level "l", find all its neighbors, and push them onto a stack stored in level "l+1".

   Important: if your task allows finding paths that contain loops, do NOT check if you already visited any node you add. If it does not allow loops, use a hash of visited nodes to not add any node twice**

3. Stop when you end level "N-1".

4. Loop over all the nodes you just added to stack at index "N" and find your destination node. If found: success, if not, no such path.

Please note that if by "every node can be connected" you are implying a FULLY CONNECTED graph, then there exists a mathematical answer not involving actually visiting nodes

(however, the formula is too long to write in the text-entry field of StackOverflow)