algorithm - 迭代加深DFS以查找简单路径

所有人！
我想使用迭代深化dfs来找到图中两点之间的所有简单路径。
我阅读了算法并理解了它为什么有利于搜索。
但有一件事我需要弄清楚，似乎这个算法不太适合找到两点之间的所有简单路径。
因为有的路短得多，有的路长得多那么如何决定何时停止呢？
我现在正在运行一个程序，考虑到这些事情。
程序是这样的

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
      */
   }
}

现在，这个程序出了点问题，我正试图修复它。
同时，我想听听你的建议。
迭代深化DFS可以用来在大型图形上找到速度相对较快的简单路径吗？
如果是，请分享你的经验。
如果没有，请告诉我什么算法是最好的？
提前谢谢！

最佳答案

不。如果你在寻找所有简单的路径，迭代深化dfs是没有意义的。只要做一个常规的DFS，因为你不关心路径长度。
常规dfs应该注意不要进入循环，这意味着它应该避免已经在潜在路径上的节点，因此找到的所有路径都是简单路径。如果您的实现不这样做，请添加一个bool向量，当您将相应的值添加到该路径时，将其设置为true；当您从递归返回时，将其设置为false，并避免已将该值设置为true的节点。
大型图上的所有路径都将变慢。在完全连通图上，路径数为~N（如果我没弄错的话）。既然这是解决方案的规模，你就不能做得更好。DFS是一个不错的解决方案它可以优化，但不会是政治上的如果需要解决现实世界中的问题，请尝试利用正在处理的图形的某些特殊性（例如节点之间的低连接，或无法连接到目标或源的大区域）。

关于algorithm - 迭代加深DFS以查找简单路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35937776/