「最短経路検索アルゴリズムの MapReduce 実装」を探していました。
ただし、「ノード x から y への最短距離を計算した」ことがわかったすべてのインスタンスは、「xabcy のような実際の最短パス」を実際に出力するものはありませんでした。
私が達成しようとしているのは、何百ものノードを持つグラフがあり、さまざまなノード間の最短経路で頻繁にパターン分析を実行する必要があるということです。これは私が取り組んでいる研究プロジェクトのためのものです。
誰かが私にいくつかの実装（存在する場合）を指摘したり、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 ループです。
レデューサーでは、グループ化された値を反復しながらどこかで最低を更新します。そこで、最小値に更新された頂点によってキー頂点のソース頂点を設定する必要があります。
実際には、いくつかの頂点クラスを私のブログ のソース から、またはリポジトリから直接取得できます: ソース
多分それはあなたを助けるでしょう、それはまったくメンテナンスされていないので、特定の質問がある場合は私に戻ってきてください.
Apache Hama を使用した BSP の同じアルゴリズムを次に示します。
https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/SSSP.java