Tra*_*man 2 algorithm graph shortest-path directed-acyclic-graphs longest-path
在非循环图中,我试图找出两个给定节点之间是否存在长度为L的路径.我的问题是,在这种情况下使用的最佳和最简单的算法是什么.
请注意,该图最多包含50个节点和100个边.
我试图使用DFS找到所有路径,然后检查两个节点之间是否存在该路径,但我从在线判断中得到了"超出时间限制"的答案.
我还使用了统一成本搜索算法,但我也得到了否定回应.
我需要一种更有效的方法来解决这个问题.谢谢.
我不知道它是否会比DFS方法更快 - 但它会提供一个可行的解决方案:
将图形表示为矩阵A,并计算A^L- 当且仅当时,存在i和j之间的长度L的路径A[i][j] != 0
此外,关于DFS解决方案:您不需要在DFS中找到所有路径 - 您应该将自己限制为长度<= L的路径,并且一旦长度超过所需长度,通过此修剪一些搜索.一旦长度为L的路径到达目标,您也可以逃避搜索.
另一种可能的优化可以是双向搜索.