一个巨大图形的直径

Question

我有一个巨大的图表，希望使用多台机器进行处理。

我想计算图表直径是否大于50。

如何分割数据并编写并行算法以计算它？（返回布尔值）

图表直径是任意两个顶点之间的最大距离。

- DuduAlul

---

我希望能够找到一个适用于两种情况的解决方案，总的来说，它确实可以做到... - DuduAlul

Answer 1

要解决这个问题，标准的方法是使用全对最短路径算法——弗洛伊德-沃舍尔算法 是一个不错的起点。如果想要使用Hadoop的话，还有另一种选择，可以参考这里。

- Joel

---

@MrOhad，你可以在这里找到 Floyd-Warshall（并行）的源代码：http://pcl.cs.ucla.edu/projects/maisie/tutorial/programming/samples/apsp.m。这里有解释：http://pcl.cs.ucla.edu/projects/maisie/tutorial/programming/。 - Dr. belisarius

实际上，他不想要一个并行算法，他想要一个分布式算法。因此有了Hadoop链接。 - Joel

我理解了弗洛伊德-沃舍尔算法，这是一个很棒的算法！:-) 问题是，我该如何将它分割到多台计算机上？它是一个动态规划算法，它只是按行（n次）填充矩阵... 我很想听听你的意见。此外，这是一种很好的方法来找出每对顶点之间的最短路径，我实际上正在寻找列表中的max()值，这真的是最好的方法吗？谢谢！ - DuduAlul

另一个回答已经解决了这个问题。 - Joel

这里有几种并行F-W算法的方法：http://www.mcs.anl.gov/~itf/dbpp/text/node35.html - DuduAlul

Answer 2

请看：

请查看图直径算法的并行实现

另外还有: 并行图算法

- Dr. belisarius