bellman fordアルゴリズムで負のエッジが許可されるのはなぜですか？

Question

なぜdijkstraアルゴリズムで負のエッジは許されないのに対し、bellman fordアルゴリズムでは負のエッジサイクルが許されますか？

Answer 1

あなたの質問はすべて、教室の質問と思われます。 1.教科書と2.）クラスノートを参照してください。 1つまたは両方の場所で答えが明確に文書化されています。

Answer 2

許可しますか？ Bellman-Fordアルゴリズムは、負の重みを持つ（Dijkstraアルゴリズムではサポートされていません）のの異なるエッジを許可しますが、いずれのアルゴリズムも負の値を受け入れません。サイクル。最短経路問題は、負のサイクルの存在下では意味をなさないので、そのようなアルゴリズムで負のサイクルを「許可」する意味のある方法はありません。

ベルマンフォードアルゴリズムは、負のサイクルの存在を検出し、実行を中断することができます（この場合、正しい解決策が存在しないため、中断します）。