我有一个包含数百万个节点的大图。我想检查节点“A”是否可以从节点“B”以少于 4 个跃点到达。如果可能的话，我想要最短的路径。解决此问题的最佳方法（或算法）是什么？
问问题
2778 次
3 回答
7
请注意，如果图表未加权（如您的问题所示） - 一个简单有效的BFS将足以找到从源到目标的最短路径。
此外，由于您有一个源和一个目标- 您可以应用双向 BFS，这比 BFS 更有效。
算法思想：从源和目标同时进行 BFS 搜索：[BFS 直到两者的深度 1，直到两者的深度 2，......]。
当你找到一个顶点 v 时，算法将结束，它位于 BFS 的前面。
算法行为：终止算法运行的顶点 v 将恰好位于源和目标之间的中间。
在大多数情况下，该算法将产生比源代码中的 BFS 更好的结果[解释为什么它比 BFS 更好]，并且如果存在，肯定会提供答案。
为什么从源头上比 BFS 更好？
假设源到目标的距离为k，分支因子为B[每个顶点都有 B 条边]。
BFS 将打开：1 + B + B^2 + ... + B^k顶点。
双向 BFS 将打开：2 + 2B^2 + 2B^3 + .. + 2B^(k/2)顶点。
对于大的 B 和 k，第二个显然比第一个好得多。
（*）双向搜索的解释取自我发布的另一个答案
于 2012-11-01T14:12:15.073 回答
3
在您没有关于一个节点接近目标的可能性的额外信息的图中，找到两个节点之间最短路径的最佳算法是Dijkstra 算法。您可以轻松地修改此算法以在 3 跳后退出，以避免在您不感兴趣的结果上浪费计算。
如果您确实有一些关于给定节点接近目标的可能性的额外信息，您可以使用A* search，它使用节点到目标距离的启发式算法来提高其运行时性能。
于 2012-10-31T06:19:08.707 回答
1
如果您需要少于 3 跳的路径，那么所有可能的路径是 A（A=B）、AB（节点相邻）、AXB（X 是与两端相邻的节点）。所以不需要任何复杂的算法。首先，测试 A=B，第二，测试 A 和 B 是否相邻，第三，尝试找到与 A 和 B 都相邻的 X（例如端点邻接集的交集）。
于 2012-11-01T13:24:52.210 回答