2

私は古いアルゴリズムのメモを確認していて、この証拠に出くわしました。それは私が持っていた課題からのものであり、私はそれを正しく理解しましたが、確かに証拠が不足していると感じています。

問題はprove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

私の証明は次のようになります：

矛盾による証明。まず、d値'i'でQから頂点をプルするとします。次回は、d値が「j」の頂点をプルします。iを引いたとき、d値を確定し、開始頂点sからiまでの最短経路を計算しました。正のエッジウェイトがあるため、パスに頂点を追加するときにd値を縮小することはできません。Qからiを引いた後、より小さなd値でjを引く場合、jを介してiに到達できる可能性があるため、iへの最短経路がない可能性があります。ただし、iへの最短経路はすでに計算されています。可能なパスは確認しませんでした。保証されたパスはもうありません。矛盾。

この証明をどのように改善できますか？またはさらに良いことに、別のアプローチがありますか？かなり弱いようです:)

編集：申し訳ありませんが、この場合、私の優先キューは最小ヒープで実装されています

4

1 に答える 1

1

これらを確立しましょう（これらは基本的にアルゴリズムの定義であるため、これらはすべて真です）：

  1. ダイクストラのアルゴリズムの優先度付きキューは、アルゴリズムの各反復で最小のd値を持つノードを提供します。
  2. 負のエッジウェイトはありません。
  3. ノードがデキューされると、キューに戻ることはありません。
  4. デキューされたノードのd値は最終的なものであり、それ以降は変更されません。

（1）を続けると、各ノードのd値はノードのd値に依存するため、（2）が適用されると仮定すると、そのデキューされたノードのd値は少なくとも抽出された前のd値と等しくなります。その前にデキューされます。これは一種の再帰的定義です。（3）と（4）が正しいので、この再帰的定義は、d値が0の開始ノードで終了します。
したがって、各ノードのd値が少なくとも彼の前のd値と等しい場合、 （1）は引き続き適用され、優先キューから抽出されたd値のセットは減少しません。

（これとあなたが書いたものを読んだ後、それは基本的に同じですが、私が思うに少し良く提示されました）

于 2010-04-14T15:06:36.823 に答える