\manpage {b\_node\_pq} {n} {Bounded Node Priority Queues} 
 
\definition
An instance of the data type \name\ is a priority queue of nodes with
integer priorities with the restriction that the maximal difference of 
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. 

 
\creation PQ 
 
\create { }
   { introduces a variable \var\ of type \name\ and initializes
              it with the empty queue with default minimum node $nil$.  }
 
 
\create {(node\ v)}
   { introduces a variable \var\ of type \name\ and initializes
              it with the empty queue with default minimum node $v$.  }
 
 
\operations 1.3 4.5 
 
\op  node del\_min {()}
           {  removes the node with minimal priority from \var\ and returns
            it (the default minimum node if \var\ is empty).  } 
 
 
\op  void insert {(node\ w, \ int\ p)}
           {  adds node $w$ with priority $p$ to \var.  }
 
 
\op  void del {(node\ w)}
           {  deletes node $w$ from \var.  }
 
 
\implementation
Bounded node priority queues are implemented by cyclic arrays of
double linked node lists. 
 
\example
Using a $b\_node\_pq$ in Dijktra's shortest paths algorithm.
\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

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];
}

\endgroup

 
