algorithm - 複数の宛先の最大加重パス

Question

有向巡回加重グラフがあります。X頂点の長さで、いくつかの重みが最も高いパスを見つけたいのですが、目的地が何であるかは気にしません。私は最高のコストを見つけたいだけです。

Answer 1

これは、動的計画法のようなアルゴリズムで解決できます。

ノードは数百しかなく、X はラウンド 10 であるため、各ノード v にサイズ X の配列 Fv を割り当てることができ、Fv[i] はソースからノード v までの長さ i の最大コストを表します。

ソースにしましょう。Fs[0] = 0 に設定し、他のすべての Fs[i] = -infinity に設定します。

他のすべての配列は-infinity配列として初期化されます。

今、

ノード v ごとに、次の更新を行います。

Fv[i] = max{Fv[i], Fw[i-1] + コスト(w, v) | ここで、w は v の隣人です}

上記の更新を少なくとも X 回繰り返し、すべての v について Fv[X] をチェックして、必要な最大値を取得します。

いくつかの追加情報を使用してパスを取得できますが、これは非常に簡単です。

上記のアルゴリズムはBellman-Ford Algorithmの特殊なケースです

Answer 2

Bellman-Ford アルゴリズムを使用して、必要なことを行うことができます。