在无环图中，我试图找出两个给定节点之间是否存在长度为 L 的路径。我的问题是，在这种情况下使用的最好和最简单的算法是什么。
请注意，该图最多有 50 个节点和 100 条边。
我尝试使用 DFS 查找所有路径，然后检查两个节点之间是否存在该路径，但我从在线法官那里得到了“超出时间限制”的答案。
我也使用了统一成本搜索算法，但我也得到了否定的回应。
我需要一种更有效的方法来解决此类问题。谢谢你。
问问题
2409 次
4 回答
5
我不知道它是否会比 DFS 方法更快 - 但它会提供一个可行的解决方案：
将图表示为矩阵A，并计算A^L- 当且仅当 i 和 j 之间存在长度为 L 的路径A[i][j] != 0
此外，关于 DFS 解决方案：您不需要找到DFS 中的所有路径- 您应该将自己限制在长度 <= L 的路径中，并在长度超过所需长度后通过此修剪一些搜索。一旦长度为 L 的路径到达目标，您也可以逃避搜索。
另一种可能的优化可能是双向搜索。
- 找到从源到它们的路径长度为 L/2 的所有顶点。
- 接下来，找到从它们到目标的路径长度为 L/2 的所有顶点（反向图上的 DFS）
- 然后，检查是否有两个集合共有的顶点，如果有 - 你得到了一条从源到目标的长度为 L 的路径。
于 2012-06-20T16:54:03.997 回答
2
由于图是非循环的，您可以对顶点进行拓扑排序。让我们命名起始顶点 A 并结束顶点 B。
现在核心算法开始：对于每个顶点计算从 A 到该顶点的所有可能距离。一开始有一条从 A 到 A 的路径，长度为零。然后按拓扑顺序取顶点。当您选择顶点 x 时：查看每个前驱并在此处更新可能的距离。
这应该在 O(N^3) 时间内运行。
于 2012-06-20T19:10:46.933 回答
0
您可以使用修改后的 Dijkstra 算法，而不是为每个顶点保存到原点的最小距离，而是保存小于或等于所需距离的所有可能距离。
于 2012-06-21T07:27:28.623 回答
-1
我相信您可以使用以下算法找到树中最长的路径。这假设您的图表是连接的，如果不是，您需要在每个连接的组件上重新运行它：
- 选择一个任意节点，A。
- 从 A 执行 BFS（或 DFS）以在树中找到离 A 最远的节点，将此节点称为 B。
- 从 B 做一个 BFS（或 DFS），在树中找到离 B 最远的节点，称这个节点为 C。
- 从 B 到 C 的路径是树中最长的路径（可能并列最长）。
显然，如果这条路径比 L 长，那么您可以缩短它以找到长度为 L 的路径。
于 2012-06-20T18:28:54.300 回答