OR 215Spring 1999

Network FlowsM. Hartmann

THE RADIX HEAP IMPLEMENTATION OF

DIJKSTRA'S SHORTEST PATH ALGORITHM

Priority Queues

Radix Heaps

R-heap Implementation

Further Results

A QUICK REVIEW OF DIJKSTRA'S ALGORITHM

PT

procedure DIJKSTRA;

begin

INITIALIZE;

while T  do

begin

FINDMIN; {select i with d(i) = min {d(k) : kT} }

P := P  {i}; T := T \ {i};

UPDATE(i); {d(j):= min{d(i)+cij,d(j)} for (i,j)A(i)}

end;

end

PRIORITY QUEUES

T is a set (the set of nodes with temporary labels) and for each i T, there is an associated integer d(i).

  • In a queue, the items are selected in FIFO order.
  • In a priority queue, items are selected in the order of their priority (the “priority” of i T is d(i) in Dijkstra's).

Standard Priority Queue Operations:

  • CREATE(T): Creates an empty priority queue.
  • FINDMIN(T): Finds the element in T with

minimum d( ).

  • DELETEMIN(T): Deletes this element.
  • INSERT(i,T): Inserts element i into the set T.
  • UPDATE(i,,T): Reduces d(i) by .

The standard implementation has the following running times per operation:

CREATE, FINDMIN: O(1)

DELETEMIN, INSERT, UPDATE:O(logn)

APPLICATIONS OF PRIORITY QUEUES

  1. Hospital emergency rooms.
  1. Shortest path problem:
  • FindMin: called n times for O(n log n) steps.
  • Update d(i): called m times for O(m log n) steps.
  • Total operations: O(m log n) using standard implementations of priority queues.
  1. Used in determining how to allocate processor time on time-shared computers.

Radix Heap: A specialized implementation of priority queues for the shortest path problem.

A useful property (of Dijkstra's algorithm): The value of the minimum temporary label d( ) is monotonically non-decreasing.

RADIX HEAPS IN ACTION

123456

d( ) / 0 / 13 / 0 / 15 / 20 / 

Radix Heap Storage Rule: Store node j in the Bucket k such that d(j)  Range(k). (These ranges change, and

whenever they do, the nodes may have to be moved.)

123456

d( ) / 0 / 13 / 0 / 15 / 9 / 

We need to redistribute the nodes! This is accomplished by changing the ranges of the buckets.

DATA STRUCTURES

Choose K so that 2K > nC. (In the example, K=7.)

  • Bucket(k) for k = 0 to K+1;
  • Range(k)for k = 0 to K+1;
  • Assign(j)for k =1 to n;

Relationship: node j T is stored in Bucket k if and only if Assign(j) = k if and only if d(j) Range(k).

Initially Range(0)=0, Range(k) = [2k-1, 2k -1] for k = 1 to K and Range(K+1) = ; i.e., it has nodes with d(j) = .

Comment: These data structures can be initialized in O(n+K) time.

We need to show how to do FINDMIN and UPDATE(i).
procedure FINDMIN;

begin

Current := 0;

while Bucket(Current) =  do Current := Current + 1;

if Current  2 then REDISTRIBUTE(Current);

{ all the key action takes place in the above subroutine }

let i be a node in Bucket(Current);

end

procedure UPDATE(i);

begin

for each (i,j) A(i) if d(j) > d(i) + cij then

begin

d(j) := d(i) + cij and Pred(j):=i;

if d(j)  Range(Assign(j)) then REINSERT(j);

end;

end

procedure REINSERT(j);

begin

k := Assign(j)

delete node j from Bucket(k);

while d(j)  Range(k) do k := k-1;

add node j to Bucket(k);

Assign(j) := k;

end

procedure REDISTRIBUTE(Current);

begin

dmin: = min{d(j): j  Bucket(Current)};

Range(0) := {dmin};

let U = Max_Range(Current);

for k = 1 to Current -1 do

Range(k) := [ 2k-1 + dmin, min{2k-1+ dmin,U} ];

{ REDISTRIBUTE Bucket(Current) }

for each j  Bucket(Current) do REINSERT(j);

Current := 0;

end

Lemma 1. The cumulative time spent in all calls to REINSERT is O(m+nK).

Proof: Except for the while loop, the total time would be O(m). For each time that the “while loop” is executed during the reinsertion of node j, Assign(j) decreases. This can happen at most K times for node j, and at most nK times overall.

123456

d( ) / 0 / 13 / 0 / 15 / 9 / 


123456

d( ) / 0 / 13 / 0 / 15 / 9 / 13



complexity

THEOREM:The R-heap algorithm determines the minimum path tree in O(m+nlognC) steps.

Outline of the Proof:

  • The time for reinsertion is still O(m+nK) even if we take into account the reinsertions caused by redistribution of the ranges.
  • The time to update the bucket ranges is O(K) per redistribution, or O(nK) in total.
  • The only potential bottleneck is locating dmin in Bucket(Current). This time is dominated by the total time for reinsertion. We see this as follows:

Let B be the number of nodes in Bucket(Current) during a given execution of REDISTRIBUTE. The scanning time to find dmin is O(B), but the time to reinsert the nodes is O(1) for each of the B nodes.

FURTHER RESULTS

  1. We can reduce the number of buckets to O(logC) if we are a little careful in handling the highest index bucket. The resulting running time is O(m+nlogC).
  1. By using buckets with sub-buckets, we can further reduce the running time to O(m+ nlogC/ loglogC). Moreover, this algorithm is quite practical.
  1. By using a generalization of Fibonacci heaps (deve-loped by Fredman and Tarjan) we can further reduce the running time to O(m+ nlog1/2C).
  1. Let w = (1+ min{cij:(i,j) A}). If we are a little more clever, we can replace C in the time bounds by C/w.

Which is the faster algorithm:

Radix heaps (improved version) at O(m+ nlog1/2C),

or Fibonacci heaps at O(m+nlogn)?

OTHER ISSUES

Empirical Results:

In preliminary testing, the R-heap algorithm took

20% more time than a variant of Dial’s algorithm,

and about 50% more time than Pape’s algorithm

(a LIFO/FIFO hybrid with a (2n) running time).

The significance of data structures:

Algorithms (such as Dijkstra's) can often be described at a “high level” (or more abstract level) such that its running time is not apparent. Improved running times are often achieved through clever data structures.