負のウェイトサイクルでのFloyd Warshallアルゴリズムの時間複雑度

Question

負のウェイトサイクルがグラフにあるときに最小距離を見つける方法がないことを知っています。最小距離の意味はありません。私の質問は、負のウェイトサイクルを持つグラフでFloyd Warshallアルゴリズムをフィードするとどうなりますか？ O（n ）で無期限に実行されたり、終了したりしますか？

Answer 1

ありがとうございましたWikipedia
Floyd-Warshallアルゴリズムには、現在の重量または最大重量に基づいた条件はありません。
アルゴリズムは、すべての頂点ペアを通過し、距離を計算するだけです。 答えはいいえ、無期限に実行されません。
確かにアルゴリズムは間違った答えを返します（負のサイクルの頂点には負の距離があります）。例えば、頂点からそれ自身までの距離は負であろう。

また、このアルゴリズムは、負のサイクル検出にも使用できます。