我在大数据分析中遇到了一个问题，我正在使用 Dijkstras 算法为具有超过 175K 个节点的图找出路径。但问题是我不知道特定的源和目的地是否存在路径。我必须为大约 1000 个来源和目的地执行此操作。但我不能随机选择它们，因为我不确定它们之间是否存在路径。我不确定如何处理。在 MapReduce 环境中执行一次算法在本地大约需要 15 分钟的时间。因此，反复试验不是一种选择。只有我们能找到至少 1000 个来源和目的地是为了找到循环(？)或强连接组件？它是否正确 ？我希望我的问题很清楚。
我基本上是在寻找 1000 对来源和目的地，在该大小的图中存在路径
最佳答案
我建议随机选择 1000 个源节点，然后为每个节点运行 Breadth-First-Search直到您访问了 k 个节点。然后，选择您要访问的下一个节点并将其设置为该源的目的地。
使用此方法，您可以保证每个目的地都可以从该源到达。
关于algorithm - 在 175K 节点的图中找出路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13695432/