我有大约70,000个节点和250,000条边，而且图不一定是连通的。显然使用高效的算法至关重要。你有什么建议？
另外，我希望知道如何在几台机器之间分配任务——这种问题是否可能？
谢谢。
寻找图中每对节点之间的所有最短路径
9
- awegawef
4
你说得对，这不是一个作业问题，只是一个为了好玩的项目。我没有考虑过近似值，但在这种情况下，我需要获得两个节点之间的实际路径，而不仅仅是距离。我不认为近似值在这种情况下确实有帮助，但如果有的话，我很想听听怎么做的。 编辑：这是对被删除评论的回应。没关系。 - awegawef
抱歉，我刚刚把它删除了！我只是想问一下你是否考虑过使用近似解决方法，但后来我决定不问了，因为你已经接受了一个答案。 :) - Mark Byers
在这个上下文中，近似值是指一条路径，它不能保证是最短的，但保证不会比最短路径长超过x%。 - Mark Byers
你有18GiB的内存来存储解决方案吗？你真的需要全部吗？ - baol
4个回答
4
MapReduce是一种非常适合分布式算法的技术，但可能有些过于强大。如果您对此感兴趣，请参考这个讲座或者这篇博客文章以获取灵感。实际上，当我学习MapReduce时，这是其中的一个最早的例子之一。
对于250k个边和70k个节点来说，似乎这个图相对稀疏，Dijkstra算法每个节点的运行时间为O( E + V log V )，所有源的全运行时间为O( VE + V^2 log V )。这应该已经足够快了，但是对于Dijkstra算法也存在通常的注意事项（负边缘）。
如果您的问题涉及负权重但不涉及负循环，则还可以查看Johnson算法。具体来说，它也可以进行分布式处理，因为它对重新加权的图进行处理，然后从每个节点运行Dijkstra算法。
- Larry
3
后面的链接没有显示出来：http://en.wikipedia.org/wiki/Dijkstra's_algorithm 和 http://en.wikipedia.org/wiki/Johnson's_algorithm - Larry
你应该了解一下Markdown语法，以便格式化你的帖子。无论如何，我还是给你点赞了。 - Mark Byers
我的意思是，似乎存在链接限制。 - Larry
4
你可以使用Floyd-Warshall算法，它可以解决这个问题。
复杂度为O(V^3)。
还有Johnson's算法，其复杂度为O(V^2*log V + VE)。后者也很容易分配，因为它运行Dijkstra算法V次，可以并行完成。
复杂度为O(V^3)。
还有Johnson's算法，其复杂度为O(V^2*log V + VE)。后者也很容易分配，因为它运行Dijkstra算法V次，可以并行完成。
- Mark Byers
4
嗯，但它的复杂度为
O(n^3)。可能不是非常高效。 - dirkgently@dirkgently：实际上，复杂度大约是O（V ^ 2 + V * E）。这不是火箭般的快速，但如果您想要V ^ 2输出，可能无法获得更多。 - jpalecek
@jpalecek：我指的是原始帖子，特别是弗洛伊德-沃舍尔算法。 - dirkgently
哇，Floyd-Warshall是一个简洁的算法。如果我的节点不是那么多，我肯定会选择它。 - awegawef
1
有两种并行化这个问题的天真方法：
1）识别子组件并将其分布在不同的计算机上。两个不同组件之间的路径长度是未定义的。
2）在不同的计算机上加载图形，并为每个计算机提供要计算所有最短路径的节点列表。一个节点的结果不依赖于另一个节点的结果，因此可以并行化此问题。
优点：实现起来不太困难，但如果您只想解决一次此问题，则应仅以此方式执行。如果这是一个经常出现的问题，那么您可能需要查看分布式算法。
使用igraph，它是用C编写的，非常快速，您可以使用Python作为包装语言。
- DrDee
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接