3

I have been looking for "MapReduce implementation of Shortest path search algorithms".

However, all the instances I could find "computed the shortest distance form node x to y", and none actually output the "actual shortest path like x-a-b-c-y".

As for what am I trying to achieve is that I have graphs with hundreds of 1000s of nodes and I need to perform frequent pattern analysis on shortest paths among the various nodes. This is for a research project I am working on.

It would be a great help if some one could point me to some implementation (if it exists) or give some pointers as to how to hack the existing SSSP implementations to generate the paths along with the distances.

4

1 回答 1

1

基本上，这些实现与某种消息传递一起工作。因此消息在 map 和 reduce 阶段之间发送到 HDFS。

在 reducer 中，它们按距离分组和过滤，最小的距离获胜。在这种情况下更新距离时，您必须设置消息来自的顶点（嗯，可能是某个 ID）。

因此，每个顶点都有额外的空间要求，但您可以重建图中每条可能的最短路径。

根据您的评论：

很可能是

我需要编写另一个顶点对象类来保存这些附加信息。感谢您的提示，尽管如果您能指出我可以在何时何地捕获最小重量来自何处的信息，这将非常有帮助，可能来自您博客的任何内容:-)

是的，对于 Apache Hama 来说，这可能是一个很酷的主题。大多数实现只是考虑成本而不是真正的路径。在您的情况下（来自您上面链接的博客），您将必须提取一个顶点类，该类实际上将相邻顶点保存为LongWritable（可能是一个列表而不是文本对象上的这个拆分）并简单地添加一个父或源 id 作为场（当然也是LongWritable）。您将在映射器中传播时设置此项，即在当前关键节点的相邻顶点上循环的 for 循环。

在化简器中，您将在迭代分组值时更新某处的最低值，在那里您必须将关键顶点中的源顶点设置为更新为最小值的顶点。

您实际上可以从我的博客中获取一些顶点类： Source 或直接从存储库中获取： Source

也许它对你有帮助，它是完全无人维护的，所以如果你有一个具体的问题，请回来找我。

这是 BSP 中与 Apache Hama 相同的算法：

https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/SSSP.java

于 2012-08-14T14:52:53.427 回答