Algorithmic Solutions > LEDA > LEDA Guide > Graphs and Related Data Types > Bounded Node Priority Queues

Bounded Node Priority Queues

The data type b_node_pq<N> is a priority queue of nodes with integer priorities. The size of the interval containing all priorities is restricted to at most N, that is, the priorities can be in the interval [i,i+N]. b_node_pq<N> is a specialized version of Node Priority Queues.

In a Node Priority Queue the node with the minimum priority can be accessed very efficiently.

Example of how to use a bounded node priority queue

Strengths

  • even more efficient than node priority queues

Disadvantages

  • size of the interval containing all priorities is restricted to at most N
  • minimum priority can not be decreased
  • every node may be contained in the queue at most once.
  • very restricted interface, operations are tailored for Dijkstra's shortest path algorithm

Tips

  • Prefer bounded node priority queues to node priority queues if possible.

See also:

Node Priority Queues

Priority Queues


Manual Page Bounded Node Priority Queues




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH