cycle - ダイクストラのアルゴリズムが負の重みサイクルを持つ有向グラフで実行された場合はどうなりますか？

Question

ダイクストラがランダムな頂点から実行され、パス上で負の重みのサイクルに遭遇するとします。サイクルをループしてコストを可能な限り小さくすることはできますが、ダイクストラの不変条件は、訪問したノードを「再訪問」することではないため、無限ループは発生せず、ダイクストラは終了しますか？

Answer 1

問題は、ダイクストラのアルゴリズムが終了しないことではなく、負の重みを持つグラフではダイクストラのアルゴリズムがまったく機能しないことです。理由の説明については、この回答を参照してください。