data-structures - 負の重みサイクルを持つグラフの単一ソースの最短パスを取得する方法

Question

ねえ、「単一ソースの最短経路」問題のベルマンフォードアルゴリズムを研究しています。

今、負の重みサイクルを持つグラフの解決策を見つける必要がある時点で立ち往生しています。

しかし、ベルマンフォードのアルゴリズムはここでは機能しません。

誰かが私に何をすべきかを提案できますか。負の体重サイクルの問題を解決するには?

御時間ありがとうございます。

Answer 1

Bellman-Ford が検出できる、原点から到達可能な負のサイクルがある場合、エッジの繰り返しを許可するか許可しないかの 2 つの選択肢があります。エッジの繰り返しを許可すると、最短パスは無限に負になると見なされる可能性があります。そうでない場合、問題は NP 完全です。ウィキペディアから：

最短経路問題の NP 完全バリアントの 1 つは、エッジが繰り返されないように、G の最短経路 (負のサイクルを含む) を求めます。