CODEWITHSUNDEEP
algorithmsearchgraph
arslan
arslan

Reputation: 2224

Iterative deepening DFS to find simple paths

Everyone!

I want to use Iterative deepening DFS to find all simple paths between two points in graph. I read the algorithm and understand it why it is good for searching. But there is one thing i need to figure out, that it seems this algorithm is not very suitable for to find all simple paths between two points. Since there are paths which is much shorter while there are paths which are longer. so how to decided when to stop?

I am running a program right now with these things in mind. The program is like that

IDDFS(target, source)
{
   int depth=1;
   bool m_bool=FALSE;

   while(!m_bool)
   { 
      depth++;
      m_bool=dfs(target,source,allpaths,depth);
      /*
      dfs is recursive, and when return true, that means find a simple 
      path
      */
   }
}

Now, this program has something wrong, I am trying to fix it. Meanwhile, I would like to have advice on that. could Iterative deepening DFS can be used to find simple paths with relatively fast speed on large graphics? if yes, please share your experience. if no, then please suggest me what algorithm is best?

Thanks in advance!

Upvotes: 0

Views: 965

Answers (1)

Sorin
Sorin

Reputation: 11968

No. Iterative deepening DFS doesn't make sense to do if you are looking for all simple paths. Just do a regular DFS since you don't care about path length.

The regular DFS should take care to not go into cycles which means it should avoid nodes that are already on the potential path, so all paths found are simple paths. If your implementation doesn't do this add a vector of bool where you set the corresponding value to true when you add it to that path and false when you return from the recursion and avoid nodes where the value has already been set to true.

All paths on large graphs is going to be slow. On a fully connected graph the number of paths is ~N! (if i'm not mistaking). Since that's the size of the solution you won't be able to do better than that. DFS is a decent solution to it. It can be optimized but it's not going to be polinomial. If you need to solve it for a real-world problem try to exploit some particularities of the graph you're working it (like low connectivity between nodes, or large areas that can't connect to the destination or source).

Upvotes: 1

Related Questions