Iterative deepening DFS to find simple paths

Question

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!

simple path mean no repeating of nodes. I used DFS and it is slow for huge graphs, so trying this now. I want to try this first. do you think BFS work much better than this for huge graphs? — arslan
BFS would only be useful for you if you are only interested in shortest paths. otherwise stick to DFS (because of less memory usage). — MrSmith42
Finding all 'simple' paths will always be quite slow if you graph is not only spare connected because there are so many 'simple' paths between nodes. Have you a special application in mind? Maybe you do not need all paths, but ones with other restrictions than only 'simple'? — MrSmith42
@ MrSmith42, Yes, I think you are right. It gradually goes deeper, so many revisiting. — arslan

Sorin Sorin · Accepted Answer · 2016-03-11T13:18:07

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).

Iterative deepening DFS to find simple paths

1 Answers