2

グラフに負の重みを持つエッジがある場合、ダイクストラのアルゴリズムは失敗します。ただし、このルールには例外があります。有向非巡回グラフで、ソースノードを離れるエッジのみが負（他のすべてのエッジが正）の場合、ダイクストラのアルゴリズムを正常に使用できます。

さて、私の質問は、上記の例外でグラフにサイクルがある場合はどうなるでしょうか？ダイクストラは機能しないと思いますが、サイクルのある有向グラフの例を思いつくことはできません。負のエッジは、ダイクストラで機能しないソースノードを離れるエッジだけです。誰でも例を提案できますか？

4

1 に答える 1

8

説明するシナリオでは、ダイクストラのアルゴリズムは問題なく機能します。

一般的なケースで負の重みで失敗する理由は、各ステップで「閉じる」ノードを貪欲に選択し、閉じたノードが再び開かれることはないためです。

ここで、ソースが異なるノード に対してエッジをs持っていると仮定します。それらの順序を（最小にする）とします。それぞれについて、 - 「より良い」コストでからへのパスがないため、-これらの最初のノードを調査する順序は決して変わらないことに注意してください。（そしてそれは変わらないので、最短経路が実際に見つかる前に、後のノードが「閉じられた」状態になることはありません）。kk
v_1, v_2, ..., v_kv_1v_iv_ji < jsv_iv_jv_i

したがって、全体として、害はありません。エッジが「閉じた」状態になると、負のエッジはソースからのみであるため、エッジへの「短い」パスは見つかりません。

ここでは、DAGの「ソース」と同じように、 sourceあなたの質問の意味を想定しています。ソース頂点の外を意味する場合は、2つの頂点のグラフを見て、グラフに負のサイクルがあるため、問題になる可能性があります。したがって、上記の説明が機能するためには、d_in(source)=0
w(s,t) = -2, w(t,s)=1d_in(s) = 0

于 2012-10-10T00:17:25.460 に答える