Cache-oblivious shortest paths in graphs using Buffer Heap

We present the Buffer Heap (BH), a cache-oblivious priority queue that supports Delete-Min, Delete, and Decrease-Key operations in O(1/B log ₂N/B) amortized block transfers from external memory, where B is the (unknown) block-size and N is the maximum number of elements in the queue. As is common in cache-oblivious algorithms, we assume a 'tall cache' (i.e., M = Ω(B_1+∈), where M is the size of the main memory). We also assume the Decrease-Key operation only verifies that the element does not exist in the priority queue with a smaller key value, hence it also supports the insert operation in the same amortized bound. The amortized time bound for each operation is O(log N). We also present a Cache-Oblivious Tournament Tree (COTT), which is simpler than the Buffer Heap, but has weaker bounds. Using the Buffer Heap we present cache-oblivious algorithms for undirected and directed single-source shortest path (SSSP) problems for graphs with non-negative edge-weights. On a graph with V vertices and E edges, our algorithm for the undirected case performs O(V + E/B log₂ V/B) block transfers and for the directed case performs O((V + E/B) · log₂ V/B) block transfers. The running time of both algorithms is O((V + E) · log V). For both priority queues with Decrease-Key operation, and for shortest path problems on general graphs, our results, appear to give the first non-trivial cache-oblivious bounds.