Example 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 random graph with 50 nodes and 500 edges and assigns every edge a random integer weight between 1 and 100 using the edge_array<int> cost. Then the function MY_DIJKSTRA() is called for G, the first node s of G and cost. The result of MY_DIJKSTRA() is stored in the node_array<int> dist and the node_array<edge> pred. dist[v] stores the length of a shortest path from s to node v and pred[v] stores the last edge on a shortest path from s to v. The result of MY_DIJKSTRA() is illustrated for the shortest path between s and the last node t of G.

In MY_DIJKSTRA() a node_pq<int> PQ is used to store nodes of G together with a distance value. First the starting node s is inserted into PQ with distance zero. dist[s] is also set to zero. pred[v] is set to nil for all nodes v of G. In a while-loop, the node u with minimum distance is deleted from PQ and its adjacent edges e=(u,v) are examined. If v was not yet seen, it is inserted into PQ. If we found a shorter path to v using u, the priority of v is decreased in PQ. Finally, dist[v] and pred[v] are updated.

Remark: Notice that in the insert()-operation the order of priority and information (=node) in a 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/node_pq.h>
	
using namespace leda;

void MY_DIJKSTRA(const graph& G,node s, const edge_array<int>& cost,
                 node_array<int>& dist, node_array<edge>& pred)
{ 
  node_pq<int> PQ(G);

  dist[s]=0;
  PQ.insert(s,0);

  node v;
  forall_nodes(v,G) pred[v]=nil;

  while (!PQ.empty()) {
    node u=PQ.del_min();

    edge e;
    forall_adj_edges(e,u) {
      v=G.opposite(u,e);
      int c=dist[u]+cost[e];

      if (pred[v]==nil&&v!=s) PQ.insert(v,c); 
      else if (c<dist[v]) PQ.decrease_p(v,c);
      else continue;

      dist[v]=c;pred[v]=e;	  
    }
  }
}

int main()
{
  //create random graph and random edge weights
  graph G;
  random_graph(G,50,500);

  random_source S(1,100);
  edge_array<int> cost(G);
  edge e;forall_edges(e,G) S>>cost[e];

  //call MY_DIJKSTRA() with corresponding parameters
  node s=G.first_node();
  node_array<int> dist(G); 
  node_array<edge> pred(G);
  MY_DIJKSTRA(G,s,cost,dist,pred);

  //illustrate the result of MY_DIJKSTRA() for one target node t
  node t=G.last_node();
  if (pred[t]!=nil) {     //There is a shortest path from s to t
    std::cout << "The distance from ";
    G.print_node(s);
    std::cout << " to ";
    G.print_node(t);
    std::cout << " is " << dist[t] << std::endl;

    std::cout << "The shortest path is ";
	 
    list<edge> L;
    node current=t;
    while (current!=s) {     //compute shortest path from pred
      L.push_front(pred[current]);
      current=G.source(pred[current]);
    }
	
    forall(e,L) {            //print shortest path
      G.print_edge(e);
      std::cout << " length " << cost[e] << std::endl;
    }
  }

  else if (s==t) std::cout << "Source and target are identical";

  else {  
    std::cout << "There is no path from ";  
    G.print_node(s);
    std::cout << " to ";
    G.print_node(t);
  }

  std::cout << std::endl;

  return 0;
}

See also:

Shortest Paths

Edge Arrays

Node Arrays

Priority Queues

Manual Entries: