ダイクストラのアルゴリズムが負の重みのエッジでは機能しないのはなぜですか? 質問する

Question

ダイクストラのアルゴリズムを思い出してください。頂点が「閉じている」（そして開集合から外れている）とマークされると、アルゴリズムはそこへの最短経路を見つける。、このノードを再度開発する必要はありません。このパスに開発されたパスが最短であると想定されます。

しかし、負の重みの場合は、そうではない可能性があります。例:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

AのダイクストラはまずCを開発し、その後Cを見つけられなくなる。A->B->C

編集もう少し詳しい説明:

これは重要であることに注意してください。なぜなら、各緩和ステップでは、アルゴリズムは「閉じた」ノードへの「コスト」が実際に最小であると想定し、したがって次に選択されるノードも最小になるからです。

その考え方は、コストが最小となるような頂点が開いている場合、任意の正数どの頂点に対しても、最小性は決して変わりません。
正の数に対する制約がなければ、上記の仮定は正しくありません。

「閉じた」各頂点が最小であることを「知っている」ので、「振り返る」ことなく、緩和ステップを安全に実行できます。「振り返る」必要がある場合は、ベルマンフォードこれを行うための再帰的な（DP）ソリューションを提供します。

Answer 1