バケットまたはダブルバケットのデータ構造とは何ですか？

Question

私は最短経路アルゴリズムの実装についていくつか読んでおり、Double-Bucketデータ構造を持つDijkstraのアルゴリズムを実装することは良い実装です。

しかし、ダブルバケットの実装が実際に意味するものを見つけることはできません。その上にウィキペディアの記事は曖昧です。私が見たことから、それはハッシュテーブル/マップに似ています。これまで私のデータ構造やアルゴリズムクラスでこれまで聞いた事はありませんでした。

私が読んでいた特定の紙このた、

チェルカスキー、B. V.、ゴールドバーグ、A. V.、& Radzik、T.（1996）。最短経路アルゴリズム：理論と実験的評価。数学的プログラミング、73（2）、129-174。

Answer 1

バケットデータ構造は、キー値をバケットのインデックスとして使用し、同じキー値の項目を対応するバケットに格納するデータ構造です。当然、整数キー値を持つバケットデータ構造を使用することが最も理にかなっています。

Bは、バケットデータ構造であり、バケットB[x]には、キー値がxのすべてのアイテムが格納されているとします。現在知られている最短距離は、その後、それぞれ、B[3] = {u, v}とB[7] = {w} 3,3及び7であるフロンティア・セット、3つのノードu、vとwを持っている場合、一例として、最短経路問題を使用

。

• 挿入：O(1)
• 除去：O(1)
• 減少キー：O(1)
• する最小検索：最短経路問題に関連するバケットデータ構造の

  時間分析O(c)、ここで、cは最大キー値です。

ダイクストラのアルゴリズムはバケットデータ構造を用いて実装されている場合このように、あなたはmは、エッジの数であるとnは、ノードの数は、あなたの総時間の複雑さのためO(m + nc)を持っています。

---

ダブルバケット・データ構造は、ほとんどの場合、各バケットは、バケットのデータ構造を含むバケットのデータ構造を指します。