next up previous contents index
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 minimum priority is never decreasing, 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/b _node _pq.h >

Creation

b_node_pq<N> PQ introduces a variable PQ of type b_node_pq<N> 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<N> 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) 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;
    forall_adj_edges(e,v) 
    { 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 up previous contents index
Next: Graph Generators ( graph_gen Up: Graphs and Related Data Previous: Node Priority Queues (   Contents   Index
LEDA research project
2000-02-09