     Next: Graph Generators ( graph_gen Up: Graphs and Related Data Previous: Node Priority Queues (   Contents   Index

# Bounded Node Priority Queues ( b_node_pq )

Definition

An instance of the data type b_node_pq<N> is a priority queue of nodes with integer priorities with the restriction that the size of the minimal interval containing all priorities in the queue is bounded by N, the sequence of the priorities of the results of calls of the method del_min is monotone increasing, and every node is contained in at most one queue. When applied to the empty queue the del_min - operation returns a special default minimum node defined in the constructor of the queue.

#include < LEDA/graph/b_node_pq.h >

Creation

 b_node_pq PQ introduces a variable PQ of type b_node_pq and initializes it with the empty queue with default minimum node nil. b_node_pq PQ(node v) introduces a variable PQ of type b_node_pq and initializes it with the empty queue with default minimum node v.

Operations

 node PQ.del_min() removes the node with minimal priority from PQ and returns it (the default minimum node if PQ is empty). void PQ.insert(node w, int p) adds node w with priority p to PQ. void PQ.del(node w, int=0) deletes node w from PQ.

Implementation

Bounded node priority queues are implemented by cyclic arrays of doubly linked node lists.

Example

Using a b node pq in Dijktra's shortest paths algorithm.

```int dijkstra(const GRAPH<int,int>& g, node s, node t)
{ node_array<int> dist(g,MAXINT);
b_node_pq<100> PQ(t);  // on empty queue del_min returns t
dist[s] = 0;

for (node v = s;  v != t; v = PQ.del_min() )
{ int dv = dist[v];
edge e;
{ node w = g.opposite(v,e);
int d = dv + g.inf(e);
if (d < dist[w])
{ if (dist[w] != MAXINT) PQ.del(w);
dist[w] = d;
PQ.insert(w,d);
}
}
}
return dist[t];
}
```     Next: Graph Generators ( graph_gen Up: Graphs and Related Data Previous: Node Priority Queues (   Contents   Index