7

私は過去1週間、ダイクストラのアルゴリズムに取り組んできました。Javaで正しい実行コードを使用しています。最小距離の頂点を与える標準のfindMin関数の計算に配列を使用しています。明らかにそれはO（n）であり、現在はPriority Queue（Min Heaps）を使用して実装しようとしています。

私の思考プロセスは次のとおりです。

while (there are unseen Vertex)
{

    vertex= get TheVertex WithSmallest Distance Yet;//(In can be done in O(log n) using heap)

  for this vertex {

    find all of the adjacent edges and traverse them.

    for a particular vertex which is not there in heap yet{

        Simply add it in the queue;
    }
  }
}

ただし、特定の頂点がヒープ内に存在する場合、検出された最小ノードの距離を考慮して、その距離が更新される可能性があります。

今私の質問は、O（log n）時間でヒープ内の特定の要素をどのように更新するかです。

O（1）時間でその要素を見つけることができませんか？

私のような素朴な実装では、O（n）になります。

では、このボトルネックを処理するために何ができるかを誰かが提案できますか？O（log n）時間でヒープ内の特定の頂点を更新するにはどうすればよいですか？（同様に、O（1）時間で特定の要素を見つけるにはどうすればよいですか）

4

1 に答える 1

7

私はこの状況に対する2つの基本的なアプローチを知っています。

  1. 頂点の近傍を訪問するときはいつでも、それらがヒープ内にあるかどうかに関係なく、それらをヒープに挿入します。次に、ヒープからの距離が最小の頂点を取得したら、それが以前にヒープから削除されているかどうかを確認します。ある場合は、これも削除して続行します。それ以外の場合は、削除済みとしてマークし、すべてのネイバーにアクセスします。

  2. 各要素がヒープ内のどこにあるかへの明示的なポインターを保持します。次に、すでに見つけた要素に対して「decrease-key」と呼ばれる操作を実行できます。

于 2012-08-03T19:56:03.513 に答える