Dijkstraのアルゴリズムグラフを使ってこの負の重みについて正しい方法で考えていますか？

Question

私はDijkstraのアルゴリズムが負の重み付きグラフでは機能しないのを忘れてしまいました。私は、完全に探索されたノードを指すさらなるノードを持つすべての例を理解しています。しかし、この例は私の頭の中にあります。

私はそれを考えるには正しいだろう。最初にAが探索されます。 A->Bは1となり、A->Cは100となります。次にBを調べ、B->Dを2に設定します。次に、ソースに戻って最も短いパス（優先キューの先頭）が現在あるため、Dが探索されますか？

私はB->Dが100だった場合、Cは（A->Dが101あるので）最初に検討されてきただろうと言って、正しいでしょうか？

すべての説明で実際に言及しなかったことは、ノードが探索され/訪問されたことです.Dijkstraが優先キューで動作するため、これ以上更新できません。この場合、DにはCより前に訪問した理由を頭で囲むのは難しいです。

Answer 1

それは簡単です：Djikstraのアルゴリズムを使用してノードを探索している時に/訪問/これは、あなたがそれゆえ、このノードはすでに、reexploredまたは再訪することが、あなたを必要としない、そのノードへの最短経路を発見したことを意味閉じノードへの最短経路を知る。

• ABD 2
• コスト100

とACと最小のパスコスト：あなたは、Dを選択例えば

は、PQにおける2つのパスがある探求しますコストが選択されます。アークコストが常に正の場合、A-Cを通過するDへの最短経路を見つけることはできません。 Dへの最短経路が見つけられ、ノードは閉じられます。

ただし、負のアークコストが許容されている場合、この推論はすべて当てはまりません。そのため、Djikstraのアルゴリズムはそれらに対して機能しません。

Answer 2

あなたが記述しているDijkstraアルゴリズムは、正の重み関数でのみ動作すると思います。特に、Dijkstraアルゴリズムは、重み付けされた（正に）グラフ上に有効なメトリック空間構造を与える。一方、これは、任意の重み付きグラフの場合ではないようです。たとえば、2つのノードAとBと1つのエッジを持つグラフをウェイト-5で取ります。この場合、これはAとBの間の距離を与えません。あなたが説明しているように、ある種の修正されたDijkstraモデルに入ると思います。そして、あるノードから別のノードへの解釈はもはやノード間の距離。