最大コストのパスを見つける方法

Question

頂点にコストがかかる有向グラフがあります。 2つの頂点の間に最大コストのパスを見つけたいと思いますが、最小コストでパスを解くアルゴリズムしか見つかりませんでした。

また、私はJavaを使用しています。

Answer 1

1. ノーマライズすべてのコスト最小のコストは0
2. 変化よりも大きくなるように（1 /コスト）にすべてのコスト。
3. 最小コストアルゴリズムを実行します。

結果のパスは、元のグラフの最大コストパスです。

Answer 2

使用するアルゴリズムの評価関数を変更するだけです。最短パスの場合、関数はより短いパスに対して大きな値を返します。短いパスの場合は、より小さい値を返すことをお勧めします。