2

擬似コードのほとんどの部分で、通常、次のことがわかります。

  • DeleteMin (最小のキーを持つ要素を返し、セットから削除します。)

  • DecreaseKey (特定の要素のキー値の減少に対応する)

  • 最小の要素を取得するために DeleteMin が使用されているのはなぜですか?ランダムな要素ではないのはなぜですか?
  • DecreaseKey の目的は何ですか? 擬似コードでは、要素の値が変更された後に常に呼び出されます。それは何をしているのですか？
4

1 に答える 1

6

最小の要素を取得するためにDeleteMinが使用されているのはなぜですか？ランダムな要素ではないのはなぜですか？

最小性を保証するため、開いている頂点のセットから最小要素を取得して削除しますQ（後で証明で使用されます）。それがないと、最小性機能は保証されず、ソリューションは最適になりません（最短経路にはなりません）。へのパスを見つけたらv、それをから削除し、Q再び開くことはないため、取り出すエッジには、使用可能なパスが最小のエッジが必要であることに注意してください。

この（最小の）頂点については、次のようにすることに注意してください。負のエッジがない場合、x> = 0の場合にダイクストラのアルゴリズムが使用されるため 、 -vのそれぞれに対して。最小ではない他の頂点については、まだ発見されていない短いパスがないことを保証することはできません。uQ d(u) + x <= d(v)

DecreaseKeyの目的は何ですか？擬似コードでは、要素の値が変更された後に常に呼び出されます。何してるの？

最後に見つけた頂点に接続されている頂点への新しい、より良いパスを見つけた可能性があるため、この減少が使用されます。このステップは、ダイクストラのアルゴリズムが行っている緩和ステップです。ダイクストラのアルゴリズムは、各頂点までのこれまでに見つかった最短経路を常に維持していることを忘れないでください。最後のステップで、ある頂点への新しい最短経路が見つかった可能性があるためです。このステップでは、これまでに見つかった最短経路を更新しています。

于 2012-06-21T11:52:37.500 に答える