CODEWITHSUNDEEP
algorithmgraphpathgraph-theoryshortest-path
user1514730
user1514730

Reputation: 61

All paths between two nodes in unweighted undirected graph with bounded number of edges

I have unweighted directed graph G which maybe very large (thousands of nodes).

I am interested in finding all possible paths(without cycles) between specific two nodes with limited number of edges ( at maximum the path contains 10 edges). Is there any fast algorithm which can deal with this large graph.

Upvotes: 2

Views: 2149

Answers (3)

Xline
Xline

Reputation: 812

I would second @Ivaylo Strandjev's answer. The problem is all-simple paths problem. Backtracking is the way to go. Backtracking is just DFS where at certain point the algorithm backtracks to the previous node. Your requirement of max(length)=10 is the backtracking point. Here is general description:

  1. Start with any vertex v
  2. Examine v children till you get your target or have exceed the path length requirement
  3. backtrack.

This will find all paths of length at most 10 from (v,u) for any target vertex u. The number of paths could be exponential( I think it's NP-hard problem not too sure). Efficient algorithm depends upon your domain knowledge. You may incorporate heuristics to prone unpromising nodes.

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

You can modify dfs to solve this problem. Simply add another parameter - the depth at which you currently are, then cut the dfs if the path length limit was reached before target node target. To demonstrate the idea I will use recursive implementation and I will use a global array used - the nodes visited this far on the way. Also I will assume that we've stored the graph using neighborhood list representation(let's call that neList, the neighbors of node v are at neList[v]):

used[n] = {false}
neList; // neighborhoodList
limit = 10 // max path len
void dfs(int v, int depth) {
  if (depth == limit) {
    if (v == target) {
       print_path
    } else {
       return
    }
  }
  for u in neList[v] {
    if (used[u]) {
      continue;
    }
    used[u] = true
    dfs(u, depth + 1)
    used[u] = false
  }
}

You can optimize this approach a bit - first do a bfs from the target node to compute min_distance between target and all nodes. In the dfs only go to a neighbor u if depth + min_dist[u] <= limit.

Upvotes: 1

kraskevich
kraskevich

Reputation: 18546

It is not possible to do it efficiently in the worst case. Imagine a full graph. Let's count the number of paths with exactly 10 edges. It is 1 * (n - 2) * (n - 3) * ... * (n - 9) * 1 = O(n ^ 8). It is too much for a graph with a few thousands of nodes.

Upvotes: 0

Related Questions