home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _dijkstr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.8 KB  |  124 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _dijkstra.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  DIJKSTRA  (single source shortest paths)                                    *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. #include <LEDA/node_pq.h>
  28.  
  29. declare(node_pq,int)
  30.  
  31.  
  32. void DIJKSTRA(const graph& G, node s, const edge_array(int)&  cost, 
  33.                                             node_array(int)&  dist,
  34.                                             node_array(edge)& pred ) 
  35. {
  36.   /*
  37.      Dijkstra's Algorithms for integer edge costs,
  38.      computes single source shortest paths from node s for 
  39.      a non-negative network (G,cost), computes for all nodes v:
  40.      a) dist[v] = cost of shortest path from s to v
  41.      b) pred[v] = predecessor edge of v in shortest paths tree
  42.   */
  43.  
  44.  
  45.   node_pq(int) PQ(G);
  46.  
  47.   int c;
  48.   node u,v;                                                                    
  49.   edge e;                                                                      
  50.                                                                                
  51.   forall_nodes(v,G)                                                            
  52.     { pred[v] = 0;                                                             
  53.       dist[v] = Infinity;                                                      
  54.       PQ.insert(v,dist[v]);
  55.      }                                                                         
  56.  
  57.   dist[s] = 0;
  58.   PQ.decrease_inf(s,0);                                               
  59.                                                                                
  60.   while (! PQ.empty())
  61.    { u = PQ.del_min();
  62.      if (dist[u] == Infinity) break;
  63.  
  64.      forall_adj_edges(e,u)                                                    
  65.         { v = target(e);                                                      
  66.           c = dist[u] + cost[e];                                              
  67.           if (c < dist[v])                                                    
  68.            { dist[v] = c;                                                     
  69.              pred[v] = e;                                                     
  70.              PQ.decrease_inf(v,c);
  71.             }                                                                 
  72.          }                                                                    
  73.  
  74.     } // while                                                                
  75.  
  76. }
  77.  
  78.  
  79.  
  80. #ifndef NO_REAL_GRAPH_ALG
  81.  
  82. // Dijkstra Algorithms for real valued edge costs 
  83.  
  84. declare(node_pq,real)
  85.  
  86. void DIJKSTRA(const graph& G, node s, const edge_array(real)&  cost, 
  87.                                             node_array(real)&  dist,
  88.                                             node_array(edge)& pred ) 
  89.  
  90. { node_pq(real) PQ(G);
  91.  
  92.   real c;
  93.   node u,v;                                                                    
  94.   edge e;                                                                      
  95.                                                                                
  96.   forall_nodes(v,G)                                                            
  97.     { pred[v] = 0;                                                             
  98.       dist[v] = Infinity;                                                      
  99.       PQ.insert(v,dist[v]);
  100.      }                                                                         
  101.  
  102.   dist[s] = 0;
  103.   PQ.decrease_inf(s,0);                                               
  104.                                                                                
  105.   while (! PQ.empty())
  106.    { u = PQ.del_min();
  107.      if (dist[u] == Infinity) break;
  108.  
  109.      forall_adj_edges(e,u)                                                    
  110.         { v = target(e);                                                      
  111.           c = dist[u] + cost[e];                                              
  112.           if (c < dist[v])                                                    
  113.            { dist[v] = c;                                                     
  114.              pred[v] = e;                                                     
  115.              PQ.decrease_inf(v,c);
  116.             }                                                                 
  117.          }                                                                    
  118.     } // while                                                                
  119.  
  120. }
  121.  
  122.  
  123. #endif
  124.