home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / dijkstra.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.5 KB  |  125 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3. #include <LEDA/PRIO_M.h>
  4.  
  5. declare2(prio,node,int)
  6.  
  7.  
  8. declare(node_array,pq_item)
  9.  
  10. void dijkstra(graph& G, 
  11.               node s, 
  12.               edge_array(int)&  cost, 
  13.               node_array(int)&  dist,
  14.               node_array(edge)& pred,
  15.               prio(node,int)&   PQ,
  16.               int INFTY = MAXINT) 
  17. {
  18.   /*
  19.      Dijkstra's Algorithms for integer edge costs,
  20.      computes single source shortest paths from node s for 
  21.      a non-negative network (G,cost), computes for all nodes v:
  22.      a) dist[v] = cost of shortest path from s to v
  23.      b) pred[v] = predecessor edge of v in shortest paths tree
  24.   */
  25.  
  26.   node_array(pq_item) I(G);
  27.   node v;
  28.                                                                                
  29.   forall_nodes(v,G)
  30.     { pred[v] = 0;
  31.       dist[v] = INFTY;
  32.       I[v] = PQ.insert(v,dist[v]);
  33.      }
  34.  
  35.   dist[s] = 0;
  36.   PQ.decrease_inf(I[s],0);
  37.  
  38.   while (! PQ.empty())
  39.   { 
  40.     node u = PQ.del_min();
  41.  
  42.     if (dist[u] == INFTY) break;
  43.  
  44.     edge e;
  45.     forall_adj_edges(e,u)
  46.     { v = G.target(e);
  47.       if (dist[u] + cost[e] < dist[v])
  48.       { dist[v] = dist[u] + cost[e];
  49.         pred[v] = e;
  50.         PQ.decrease_inf(I[v],dist[v]);
  51.        }                                                                 
  52.      }                                                                    
  53.  
  54.    } // while                                                                
  55.  
  56. }
  57.  
  58.  
  59. #include <LEDA/ab_tree.h>
  60. #include <LEDA/rb_tree.h>
  61. #include <LEDA/k_heap.h>
  62.  
  63. declare3(PRIO,node,int,rb_tree)
  64. declare3(PRIO,node,int,ab_tree)
  65. declare2(B_PRIO,node,k_heap)
  66.  
  67.  
  68. main()
  69. {
  70.   prio(node,int)         FH_Q;
  71.   PRIO(node,int,rb_tree) RB_Q;
  72.   B_PRIO(node,k_heap)    KH_Q(1000);
  73.  
  74.   graph G;
  75.   edge e;
  76.   node v;
  77.  
  78.   for(;;)
  79.   {
  80.  
  81.   int n = read_int("# nodes = ");
  82.   int m = read_int("# edges = ");
  83.  
  84.   if (n==0) break;;
  85.  
  86.   random_graph(G,n,m);
  87.  
  88.   edge_array(int)  cost(G);
  89.   node_array(int)  dist(G);
  90.   node_array(edge) pred(G);
  91.  
  92.   v = G.choose_node();
  93.  
  94.   forall_edges(e,G) cost[e] = random(0,100);
  95.  
  96.   for(;;)
  97.   { int i = read_int("1: f_heap  2: bin_heap  3: rb_tree  --> ");
  98.  
  99.     if (i==0) break;
  100.  
  101.     float T  = used_time();
  102.  
  103.     switch(i)
  104.     {
  105.       case  1: dijkstra(G,v,cost,dist,pred,FH_Q);
  106.                break;
  107.     
  108.       case  2: dijkstra(G,v,cost,dist,pred,KH_Q,1000);
  109.                break;
  110.  
  111.       case  3: dijkstra(G,v,cost,dist,pred,RB_Q);
  112.                break;
  113.     
  114.       default: break;
  115.      }
  116.  
  117.     cout << form("time: %6.2f sec\n",used_time(T));
  118.     newline;
  119.  
  120.    }
  121.  
  122.  }
  123.  
  124. }
  125.