How to find path of exact length in graph

Question

I would like to find path of fixed length (given while running the program) in undirected graph. I'm using adjacency matrix of my graph.
I tried to use some algorithms like DFS or A*, but they only return the shortest path.

Nodes can't be visited again.

So let's say that my graph have 9 nodes and the shortest path is built from 4 nodes.
I want to have additional variable that will "tell" the algorithm that I want to find path which have 7 nodes (for example) and it will return nodes which are included in my expected path {1,2,4,5,6,7,8}.
Of course, if there is no solution for path that I want, it will return nothing (or it will return path close to my expactations, let's say 19 instead of 20).

Someone told be about DFS with backtracking, but I don't know anything about it.
Could someone explain how to use DFS with backtracking or recommend some other algorithms to solve that problem?

Solution 1

Backtracking indeed seems like a reasonable solution. The idea is to recursively find a path of the required length.

Psuedo code:

DFS(depth,v,path):
  if (depth == 0 && v is target): //stop clause for successful branch
       print path
       return
  if (depth == 0): //stop clause for non successful branch
       return
  for each vertex u such that (v,u) is an edge:
       path.append(v) //add the current vertex to the path
       DFS(depth-1,u,path) //recursively check all paths for of shorter depth
       path.removeLast() // clean up environment

The above algorithm will generate all paths of required depth.
invokation with DFS(depth,source,[]) (where [] is an empty list).

Note:

• The algorithm will generate paths that might not be simple. If you need only simple paths - you also need to maintain visited set, and add each vertex when you append it to the found path, and remove it when you remove it from the path.
• If you want to find only one such path - you should return value from the function, (true if such a path was found), and break the loop (and return true) when the return value is true.

Solution 2

The problem as stated is NP-complete. Yo can trivially solve Hamiltonian Cycle Problem, given an efficient algorithm for solving Your problem.

Therefore, no polynomnial time solution exists (unless P=NP). For an exhaustive search, exponential time solution, check @amit's answer.