algorithm - 从图中的每对节点中查找所有最短路径

Question

我有大约 70k 个节点和 250k 个边，并且该图不一定是连接的。显然，使用有效的算法至关重要。你有什么建议吗？

作为旁注，我会很感激关于如何在多台机器之间划分任务的建议——这种问题甚至可能吗？

谢谢

score 4 · Accepted Answer

MapReduce 是一个很好的分布式算法，虽然它可能有点太强大了。如果您对此感兴趣，请查看此讲座或此博客文章以获取灵感。（事实上，当我学习 MapReduce 时，这是最早的例子之一。）

对于 250k 条边和 70k 条，图似乎相对稀疏，Dijkstra 算法在O( E + V log V )每个节点上运行，整个运行时间（所有来源）为O( VE + V^2 log V ). 这应该足够快，但通常的警告适用于 Dijkstra。（负边缘。）

如果您的问题涉及负权重而不是负循环，您还可以查看Johnson 算法。具体来说，它也可以是分布式的，因为它采用重新加权的图并从每个节点运行 Dijkstra 算法。

score 4 · Accepted Answer

您可以使用Floyd-Warshall 算法。它正好解决了这个问题。

复杂度为 O(V^3)。

还有复杂度为 O(V^2*log V + VE) 的约翰逊算法。后者也很容易分发，因为它运行 Dijkstra 的算法 V 次，可以并行完成。

score 1 · Accepted Answer

并行化这个问题有两种简单的方法：
1) 识别子组件并将它们分布在不同的计算机上。来自两个不同组件的两个节点之间的路径长度是未定义的。

2）在不同的计算机上加载图，并给每台计算机一个节点列表来计算所有最短路径。一个节点的结果不依赖于另一个节点的结果，因此您可以并行化此问题。

好处：实施起来并不难，但如果你必须解决一次，我只会这样做。如果这是一个反复出现的问题，那么您可能需要查看分布式算法。

使用igraph，它是用 C 编写的，速度非常快，您可以使用 Python 作为包装语言。

score 0 · Accepted Answer

查看具有以下关键字的论文/出版物：分布式图搜索算法。这是一个可能有帮助的。

4 回答 4