169

ダイクストラの単一ソース最短経路のアルゴリズムが、エッジが非負でなければならないと仮定している理由を誰かに教えてもらえますか。

負のウェイトサイクルではなく、エッジについてのみ話します。

4

10 に答える 10

218

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

しかし、負の重みを使用すると、それは正しくない可能性があります。例えば：

       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

もう少し深い説明を編集してください：

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

その考え方は次のとおりです。コストが最小になるように頂点を開いている場合（任意の頂点に正の数を追加することにより）、最小値は変更されません。
正の数の制約がなければ、上記の仮定は当てはまりません。

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

于 2012-10-31T13:45:48.640 に答える
55

ソースを頂点Aとして以下に示すグラフを検討してください。まず、ダイクストラのアルゴリズムを自分で実行してみてください。

ここに画像の説明を入力してください

説明でダイクストラのアルゴリズムを参照するときは、以下に実装されているダイクストラのアルゴリズムについて説明します。

ダイクストラのアルゴリズム

したがって、各頂点に最初に割り当てられた値（ソースから頂点までの距離）を開始すると、

初期化

最初に、最小値を持つQ = [A、B、C]、つまりAの頂点を抽出し、その後Q = [B、C]になります。注AはBとCに向けられたエッジを持ち、両方ともQにあるため、これらの値の両方を更新します。

最初の反復

ここで、Cを（2 <5）として抽出し、Q=[B]とします。Cは何にも接続されてline16いないため、ループは実行されないことに注意してください。

2回目の反復

最後にBを抽出し、その後にQはファイです。注BはCに向けられたエッジを持っていますが、CはQに存在しないため、ここでもforループに入りませんline16。

3番目？

したがって、距離は次のようになります。

変更なし

AからCまでの最短距離は5+-10 = -5であるため、これがどのように間違っているかに注意してくださいaからbからc。

したがって、このグラフの場合、ダイクストラのアルゴリズムはAからCまでの距離を誤って計算します。

これは、ダイクストラのアルゴリズムが、Qからすでに抽出されている頂点へのより短いパスを見つけようとしないために発生します。

line16ループが行っているのは、頂点uを取得し、「ソースからuを介してvに移動できるようです。その（代替または代替）距離は、現在取得している距離[v]よりも優れていますか？そうであれば、更新しましょう。dist [v] "

それらの中で、まだQにあるuline16のすべての隣接v （つまり、 uからvに有向エッジが存在する）をチェックすることに注意してください。彼らはQから訪問したメモを削除します。したがって、xがuの訪問した隣人である場合、パスはソースからvへの可能なより短い方法とは見なされません。line14uからxへのソース

上記の例では、CはBの訪問済みネイバーであったため、パスAからBからCは考慮されず、現在の最短パスはAからC変更されません。

これは、エッジの重みがすべて正の数である場合に実際に役立ちます。これは、短くすることのできないパスを検討するために時間を無駄にしないためです。

したがって、このアルゴリズムを実行するときに、xがyの前にQから抽出された場合、パスを見つけることはできません-ありえないこれはより短いです。これを例を挙げて説明しましょう。

yが抽出されたばかりで、xがそれ自体の前に抽出されていたため、dist [y]> dist [x]になります。そうしないと、yがxの前に抽出されてしまうからです。（line 13最初の最小距離）

また、エッジの重みが正である、つまりlength（x、y）>0であるとすでに想定しているためです。したがって、 yを介した代替距離（alt）は常に大きくなります。つまり、dist [y] + length（x、y）>dist[x]です。したがって、yがxへのパスと見なされたとしても、 dist [x]の値は更新されなかったため、まだQにあるyの近傍のみを考慮することが理にかなっていると結論付けます（のコメントに注意してください） 。line16

しかし、これは正のエッジ長の仮定に依存します。length （u、v）<0の場合、そのエッジがどれだけ負であるかに応じて、での比較後にdist[x]を置き換えることができline18ます。

したがって、すべての頂点vが削除される前にxが削除されると、 dist [x]の計算は正しくなくなります。たとえば、xはvの近傍であり、それらを接続する負のエッジがあります。

これらのv頂点のそれぞれは、ソースからxへの潜在的な「より良い」パスの最後から2番目の頂点であり、ダイクストラのアルゴリズムによって破棄されるためです。

したがって、上記の例では、Bが削除される前にCが削除されたために間違いがありました。そのCは負のエッジを持つBの隣人でしたが！

明確にするために、BとCはAの隣人です。Bには単一のネイバーCがあり、Cにはネイバーがありません。length（a、b）は、頂点aとbの間のエッジの長さです。

于 2016-08-05T09:35:21.500 に答える
31

ダイクストラのアルゴリズムは、パスが「重くなる」ことしかできないと想定しているため、重みが3のAからBへのパスと、重みが3のAからCへのパスがある場合、エッジを追加する方法はありません。 3未満の重みでAからBを経由してCを通過します。

この仮定により、負の重みを考慮に入れる必要のあるアルゴリズムよりもアルゴリズムが高速になります。

于 2012-10-31T13:42:44.973 に答える
12

ダイクストラのアルゴリズムの正しさ：

アルゴリズムの任意のステップに2セットの頂点があります。セットAは、最短経路を計算した頂点で構成されています。セットBは、残りの頂点で構成されます。

帰納的仮説：各ステップで、前のすべての反復が正しいと仮定します。

帰納的ステップ：集合Aに頂点Vを追加し、距離をdist [V]に設定する場合、この距離が最適であることを証明する必要があります。これが最適でない場合は、頂点Vへのより短い長さの他のパスが必要です。

これが他のパスが頂点Xを通過するとします。

ここで、dist [V] <= dist [X]であるため、グラフのエッジの長さが負でない限り、Vへの他のパスは少なくともdist[V]の長さになります。

したがって、ダイクストラのアルゴリズムが機能するには、エッジの重みが負でない必要があります。

于 2014-04-06T08:24:41.517 に答える
7

次のグラフでダイクストラのアルゴリズムを試してA、がソースノードでDあり、宛先であると仮定して、何が起こっているかを確認します。

Graph

アルゴリズムの定義に厳密に従う必要があり、直感に従わないように注意してください（これにより、上位パスが短いことがわかります）。

The main insight here is that the algorithm only looks at all directly connected edges and it takes the smallest of these edge. The algorithm does not look ahead. You can modify this behavior , but then it is not the Dijkstra algorithm anymore.

于 2012-10-31T19:33:55.600 に答える
7

ダイクストラのアルゴリズムは、すべてのエッジが正の重みであると想定しており、この想定は、負のエッジの可能性を考慮した他のアルゴリズム（たとえば、O（V ^の複雑さを持つベルマンフォードのアルゴリズム）よりも高速にアルゴリズムを実行するのに役立ちます（O（E * log（V）））。 3））。

このアルゴリズムは、Aがソース頂点である次の場合（-veエッジを使用）に正しい結果を提供しません。

ここに画像の説明を入力してください

ここでは、ソースAから頂点Dまでの最短距離は6である必要があります。しかし、ダイクストラの方法によれば、最短距離は7であり、これは正しくありません。

また、ダイクストラのアルゴリズムは、負のエッジがある場合でも正しい解を与える場合があります。以下はそのような場合の例です：

ここに画像の説明を入力してください

ただし、負のサイクルを検出することはなく、ソースから負の重みサイクルに到達できる場合は常に不正確な結果が生成されます。このような場合、ソースの頂点からグラフに最短経路が存在しないためです。

于 2020-08-18T14:45:47.673 に答える
3

負のサイクルを含まない負のエッジでダイクストラのアルゴリズムを使用できますが、頂点に複数回アクセスできるようにする必要があり、そのバージョンでは時間計算量が速くなります。

その場合、実際には、通常のキューを持ち、ネガティブエッジを処理できるSPFAアルゴリズムを使用する方がよいことがわかりました。

于 2020-03-29T10:47:38.010 に答える
2

ダイクストラのアルゴリズムでは、頂点が「閉じた」（そして開いたセットから外れた）とマークされると、その頂点から発生するノードはより長い距離につながると想定されるため、アルゴリズムはその頂点への最短経路を見つけ、このノードを再度開発する必要はありませんが、負の重みの場合は当てはまりません。

于 2019-01-14T22:59:12.823 に答える
2

これまでの他の回答は、ダイクストラのアルゴリズムがパスの負の重みを処理できない理由を非常によく示しています。

しかし、質問自体は、パスの重みの誤った理解に基づいている可能性があります。一般にパスファインディングアルゴリズムでパスの負の重みが許可される場合、停止しない永続的なループが発生します。

このことを考慮：

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

AとDの間の最適なパスは何ですか？

パスファインディングアルゴリズムは、パス全体の重みを減らすため、BとCの間で継続的にループする必要があります。したがって、接続に負の重みを許可すると、各接続を1回だけ使用するように制限する場合を除いて、pathfindigアルゴリズムが無効になります。

したがって、これをより詳細に説明するために、次のパスと重みを検討してください。

Path               | Total weight
ABCD               | 9
ABCBCD             | 7
ABCBCBCD           | 5
ABCBCBCBCD         | 3
ABCBCBCBCBCD       | 1
ABCBCBCBCBCBCD     | -1
...

それで、完璧な道は何ですか？アルゴリズムがBCステップを追加するたびに、総重量が2減少します。

したがって、最適なパスはA (BC) D、BCパーツが永久にループされることです。

ダイクストラの目標は（パスだけでなく）最適なパスを見つけることであるため、最適なパスを見つけることができないため、定義上、負の重みで機能することはできません。

ダイクストラは、アクセスしたノードのリストを保持しているため、実際にはループしません。しかし、それは完全なパスを見つけるのではなく、代わりに任意のパスを見つけます。

于 2019-11-12T08:04:36.287 に答える
0

次の簡単な例について、前の回答に加えて、説明にいくつかのポイントを追加します。

ここに画像の説明を入力してください

  1. ダイクストラのアルゴリズムは貪欲であり、最初にソース頂点Aから最小距離の頂点Cを貪欲に見つけ、距離d [C]（頂点Aから）をエッジACの重みに 割り当てます。
  2. 基本的な仮定は、Cが最初に選択されたため、グラフst w（AV）<w（AC）に他の頂点Vがないことです。そうでない場合、アルゴリズムによってCの代わりにVが選択されます。
  3. 上記の論理により、頂点AおよびCと は異なるすべての頂点Vに対して、 w（AC）<= w（AV）となります。ここで、明らかに、Aから 始まりCで終わり、Vを通過 する他のパスP、つまりパスP = A-> V-> ...-> Cは、長さが長くなり（> = 2）、パスPの総コストは、パス上のエッジの合計になります。つまり、P上のすべてのエッジの重みが負でない場合、Cは次の ようになります。キューQから安全に削除されました。この仮定の下では、d[C]は決して小さくなったりリラックスしたりすることはできません。
  4. 明らかに、 Pのsome.edge が負の場合、上記の仮定は当てはまりません。その場合、d [C]はさらに減少する可能性がありますが、その時点でCが 削除されているため、アルゴリズムはこのシナリオを処理できません。キューQ。 _
于 2021-11-17T23:24:45.600 に答える