我一直在寻找"MapReduce实现最短路径搜索算法"。
但是，我能找到的所有实例都"计算了从节点 x 到 y 的最短距离"，并且没有一个实例实际上输出"像 x-a-b-c-y 这样的实际最短路径"。
至于我想要实现的是，我有数百个 1000 个节点的图形，我需要对各个节点之间的最短路径进行频繁的模式分析。这是我正在从事的一个研究项目。
如果有人可以指出我一些实现（如果存在）或给出一些关于how to hack the existing SSSP implementations to generate the paths along with the distances的指示，那将是一个很大的帮助。
基本上，这些实现与某种消息传递一起工作。因此，消息在map和reduce阶段之间发送到HDFS。
在减速器中，它们按距离分组和过滤，最低距离获胜。在这种情况下，当距离更新时，您必须设置消息来自的顶点（嗯，可能是某个 ID）。
因此，每个顶点都有额外的空间要求，但您可以在图形中重建每个可能的最短路径。
根据您的评论：
是的，可能
我需要编写顶点对象的另一个类来保存它 其他信息。感谢您的提示，尽管它会非常 如果您能指出我可以在何时何地捕获此内容，请很有帮助 有关最小重量来自何处的信息，也许来自您博客的任何内容：-）
是的，可能是一个非常酷的主题，对于Apache Hama也是如此。大多数实现只是考虑成本而不是真正的路径。在您的情况下（从您上面链接的博客中），您将必须提取一个顶点类，该类实际上将相邻的顶点保存为LongWritable（可能是一个列表而不是文本对象上的这种拆分），并简单地添加父或源 id 作为字段（当然也LongWritable）。您将在映射器中传播时设置此项，即在当前键节点的相邻顶点上循环的 for 循环。
化简器中，您将在迭代分组值时更新最低值，在那里您必须通过更新到最小值的顶点在键顶点中设置源顶点。
实际上，您可以从我的博客中获得一些顶点类：源或直接从存储库：源
也许它对您有所帮助，它非常无人维护，所以如果您有具体问题，请回到我身边。
以下是 BSP 中与 Apache Hama 相同的算法：
https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/SSSP.java