実際にルートを保存するすべてのペアの最短パスアルゴリズム？

Question

私が作成したシンプルなネットワーク負荷シミュレーションツールを書き直そうとしています。今度はBoostライブラリを使用してパフォーマンスを改善しています（実装ミスを避けるため）。元のプログラムでは、ネットワーク上のすべてのソースノードからDijkstraのアルゴリズムを呼び出すことで最短経路を計算したので、Johnsonのもののような全ペアアルゴリズムがあることがわかったときに喜んでいました（私のグラフは比較的疎です、 私が想定し）。しかし、このアルゴリズムは距離行列を返すだけですが、私は実際の経路を必要としています - 少なくとも、Dijkstraのアルゴリズム実装が返す前のマップのようなものです。それを達成する方法はありますか、またはグラフの各頂点についてDijkstraを繰り返し呼び出すように戻す必要はありますか？私は一日中見渡してきましたが、何も見つかりませんでした。繰り返しアプローチに戻る前に確かめたいと思っていました。

ありがとうございます！

Answer 1

これは古い質問ですが、私もこれに対する回答を探していましたが、以前の回答が少し曖昧であることがわかりました。

距離行列があり、頂点iから頂点jまでの最短経路を探したいとします。頂点iは一連の可能な後続Nを有する。私の後継をを最小限にNで頂点である：

C（I、n）はiと隣接間のエッジのコストであり、N、およびd（N、j）が最短である

c(i,n) + d(n,j) 

距離行列によって与えられるnとjの間の距離。上の方程式を最小にする隣人nを選び、プロセスを繰り返し、iをnとNをnの近傍に置き換えます。

Answer 2

各（i、j）ペアごとに単一の最短パスがあると仮定すると、ノードwのポテンシャルが次式の可能性に等しい場合、wの前任者を仮定して簡単にパスを再構成できます。ノードuにコストまたはuwエッジを加えたもの。