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< N> 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< N> 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 bnodepq 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
Christian Uhrig 2017-04-07