[解決済み】Dijkstraのアルゴリズムが負の重みのエッジに対して機能しないのはなぜですか？

質問

ダイクストラのシングルソース最短路アルゴリズムが、なぜエッジが非負でなければならないと仮定しているのか、誰か教えてください。

負の重みのサイクルではなく、エッジのみの話をしています。

どのように解決するのですか？

Dijkstraのアルゴリズムで思い出してください。 ある頂点がquot;closed"としてマークされると（オープンセットから外れると）、アルゴリズムはその頂点への最短経路を見つけます。 そして、このノードを再び開発する必要はなく、このパスまで開発されたパスが最短であると仮定します。

しかし、負の重みの場合、そうでない場合もあります。たとえば

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

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

A から来たダイクストラは、まず C を開発し、後で A->B->C

EDIT もう少し深い説明をしてください。

これは重要なことで、各緩和ステップにおいて、アルゴリズムは「quot;closed"」ノードまでの「quot;cost"」が確かに最小であり、したがって次に選択されるノードも最小であると仮定しているからです。

その考え方は もし、openの中にコストが最小になるような頂点があるならば、その頂点に任意の 正の数 は、どのような頂点であっても、その最小性が変わることはありません。
正数の制約がなければ、上記の仮定は成り立たない。

閉じた各頂点が最小であることが分かっているので、quot;quot;quot; を振り返らずに、安全に緩和ステップを行うことができます。もし、振り返る必要があるのであれば ベルマンフォード は、そのための再帰的な（DP）解決策を提供している。