How to find path of exact length in graph

问题:

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?

回答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.

回答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.

回答3:

A single dfs ought to be sufficient:

void dfs(int start, int hops)
{
  if(hops == k && start == t)
    {
      path++;
      return;
    }
  else if(hops >= k)
    return;
  for(int w = 1; w <= n; w++)
    if(routes[start][w])
      dfs(w, hops + 1);
}

Here, k is the length of the path and routes[][] is the adjacency matrix of the graph. path is a global variable. This can account for cycles - it takes into account ALL paths of a given length. From main, call

path = 0;
dfs(source, k);
cout<<path;

Note that the number of nodes is one more than the number of hops. Also note that if the length the path is huge, this function stacks up quickly. No pun intended.

回答4:

Try finding the longest path, then cutting it to the required length. The longest path is also called as diameter of the graph. The longest path can be found by running DFS for each vertex.

回答5:

Suppose you can find a path of length d in a graph then you can run this algorithm |V| times and find the longest path which is NP-complete. So you can try the following approach -

1) approximation algorithm 2) brute force approach (more suitable for programming). Use a GPU to accelerate your code.

Also it may be of interest to you that -

there exists a linear time algorithm for DAGs.