What is a bucket or double-bucket data structure?

Question

I'm doing some reading about shortest path algorithm implementations and have been running into over and over that implementing Dijkstra's Algorithm with a Double-Bucket data structure is a good implementation.

However I cannot seem to find what a double-bucket implementation actually means, the wikipedia article on it is kind of vague. From what I've seen it is similar to a hash table/map. I never heard of this before in my data structures or algorithm classes.

The particular paper I was reading was this,

Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming,73(2), 129-174.

Answer 1

A bucket data structure is a data structure that uses the key values as the indices of the buckets, and store items of the same key value in the corresponding bucket. Naturally it makes the most sense to use the bucket data structure with integer key values.

Suppose B is a bucket data structure such that bucket B[x] stores all items with the key value of x.

Using the Shortest Paths problem as the example, if you have 3 nodes u, v and w in the Frontier set, where the currently known shortest distances are 3, 3 and 7, respectively, then B[3] = {u, v} and B[7] = {w}.

Time analysis of the bucket data structure that is relevant to the Shortest Paths problem:

• Insert: O(1)
• Removal: O(1)
• Decrease Key: O(1)
• Find Minimum: O(c), where c is the maximum key value.

Thus if Dijkstra's algorithm is implemented with a bucket data structure, you have O(m + nc) for your total time complexity, where m is the number of edges and n is the number of nodes.

---

A double bucket data structure, in most cases, refers to the bucket data structure where each bucket contains a bucket data structure.