Example Bounded Node Priority Queues

The following function implements Dijkstra's algorithm for computing the shortest paths in a graph G from a start node s to all other nodes of G.

The function main() creates a parameterized graph with 5 nodes and 5 edges and assigns every edge an integer weight between 1 and 100 using the edge entry of thze parameterized graph. Then the function dijkstra() is called to compute the length of shortest path from v[0] to v[4] in G.

In dijkstra() a b_node_pq<int> PQ is used to store nodes of G together with a distance value.

Remark: Notice that in the insert()-operation the order of priority and information (=node) in a b_node_pq and in a p_queue are inversed. It is insert(node, priority) in a node_pq, but insert(priority, information) in a p_queue.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/b_node_pq.h>

using namespace leda;

int dijkstra(const GRAPH<int,int>& g, node s, node t) 
{ 
  //compute length of shortest path from s to t in g
  //edge parameter of g is length of edge
  //length must be between 1 and 100

  node_array<int> dist(g,MAXINT);  
    //dist[v] stores (current) distance from s to v 
    //start value is MAXINT

  b_node_pq<100> PQ(t);  
    //bounded node priority queue with integer priorities
    //from interval [1,100] 
    //on empty queue del_min() returns t 
                        
  dist[s] = 0;           

  for (node v = s;  v != t; v = PQ.del_min() ) {  
    //v==t is terminating condition of for-loop
    //Either t is the node in PQ with minimum priority and 
    //we have found a shortest path from s to t.
    //Or PQ is empty, that is, there is no path from s to t in g.
    //If PQ is empty, PQ.del_min() returns t as the default node

    int dv = dist[v];  //current distance s to v

    edge e;
    forall_adj_edges(e,v) { 
      node w = g.opposite(v,e);
      int d = dv + g.inf(e);
	  
      if (d < dist[w]) { 
        //There is no PQ.decrease_key,()
        //therefore, w is deleted and reinserted
        //if dist[w]!=MAXINT)

        if (dist[w] != MAXINT) PQ.del(w);  
		
        dist[w] = d;
        PQ.insert(w,d);
      }
    }
  }

  return dist[t];
}

int main()
{
  GRAPH<int,int> G;  
    //node entry is dummy value , edge entry is weight

  node v[5];
  int i;for(i=0;i<5;i++) v[i]=G.new_node(0);

  G.new_edge(v[0],v[1],1);
  G.new_edge(v[0],v[2],3);
  G.new_edge(v[0],v[3],4);
  G.new_edge(v[1],v[2],1);
  G.new_edge(v[2],v[4],1);
  G.new_edge(v[3],v[4],2);

  std::cout << "The distance from ";
  G.print_node(v[0]);
  std::cout << " to ";
  G.print_node(v[4]);
  std::cout << " is " << dijkstra(G,v[0],v[4]) << std::endl;
  return 0;
}

See also:

Bounded Node Priority Queues

Node Priority Queues

Priority Queues

Shortest Paths

Parameterized Graphs

Manual Entries: