ソースSから宛先fまでの指向環状グラフで最も長いパスを見つけます。正の重量サイクルが存在しないと仮定します

Question

ソースSから宛先fまでの指示された循環グラフの中で最も長いパスを見つけなければなりません。正の重量サイクルが存在しないにもかかわらず、0のサイクルまたは負の重量が存在する場合でも、正の重量サイクルが存在しないと仮定します。この場合、誰かが最も長いパスを見つけるためのアルゴリズムを提案できますか。可能であればソースを引用してください。

ありがとう

Answer 1

これが機能するかどうかはわかりません（チェックする必要があります）が、次のようなことができます。

させて min = min weight on the graph.
max = max weight on the graph.
すべてのエッジ=に新しい重みを設定します wNew(e) = max - (wOld(e)-min).

これで、ネガティブなワイトがあり、重量は逆の順序です（つまり w(e1) より大きかった w(e2) 今では小さくなっています）。

最短パスを検索した場合はどうなりますか？

Answer 2

エッジの重みを無効にし、最短のパスアルゴリズム（例えば、Bellman-Ford）を実行するだけです。

ゼロウェイトサイクルが問題になる可能性があります。最短のもの（長さ、重量ではなく）を選ぶことで、パスのネクタイを破る必要があります。それを行う1つの方法は、体重をペア（ - （元の重量）、1）にし、ペアワイズを追加し、辞書編集の順序を実行することです。

参照してください 2つの頂点間の最長のパス

Answer 3

DCGを手に入れた場合、ターゲットに到達する前に永久にループすることができます。それは「最も長いパス」になります。その場合、質問は不完全であり、アルゴリズムはおそらく詳細に応じて異なって見えます。

これは宿題のように聞こえます。