3

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

ありがとう！

4

2 に答える 2

1

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

距離行列があり、頂点iから頂点jまでの最短経路を見つけたいとします。Vertex iには、可能な後継者Nのセットがあります。iの後継は、最小化するNの頂点です。

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

ここで、c（i、n）はiと隣接するnの間のエッジのコストであり、d（n、j）は距離行列によって与えられるnとjの間の最短距離です。上記の方程式を最小化する隣接nを選択し、プロセスを繰り返して、iをnに、Nをnの隣接に置き換えます。

于 2013-04-10T20:26:06.997 に答える
0

距離行列が与えられると、すべての（i、j）ペアに単一の最短経路があると仮定すると、ノードwのポテンシャルがノードuのポテンシャルにノードuを加えたものに等しい場合、wの先行がuiであると仮定してパスを簡単に再構築できます。コストまたはuwエッジ。

于 2012-06-10T19:36:18.030 に答える