Integer priority queues with decrease key in constant time and the single source shortest paths problem

摘要

We consider Fibonacci heap style integer priority queues supporting find-min, insert, and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys supports delete in O(loglogn) time. If the integers are in the range [0,N), we can also support delete in O(loglogN) time.Even for the special case of monotone priority queues, where the minimum has to be non-decreasing, the best previous bounds on delete were O((logn)1/(3−ε)) and O((logN)1/(4−ε)). These previous bounds used both randomization and amortization. Our new bounds are deterministic, worst-case, with no restriction to monotonicity, and exponentially faster.As a classical application, for a directed graph with n nodes and m edges with non-negative integer weights, we get single source shortest paths in O(m+nloglogn) time, or O(m+nloglogC) if C is the maximal edge weight. The latter solves an open problem of Ahuja, Mehlhorn, Orlin, and Tarjan from 1990.