home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _bellman.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.0 KB  |  147 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _bellman_ford.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. *  BELLMAN FORD                                                                *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25.  
  26. #include <LEDA/graph_alg.h>
  27. #include <LEDA/b_queue.h>
  28.  
  29. declare(b_queue,node)
  30.  
  31. bool BELLMAN_FORD(const graph& G, node s, const edge_array(int)& cost, 
  32.                                                 node_array(int)& dist, 
  33.                                                 node_array(edge)& pred ) 
  34.  
  35. /* single source shortest paths from s using a queue (breadth first search)
  36.    computes for all nodes v:
  37.    a) dist[v] = cost of shortest path from s to v
  38.    b) pred[v] = predecessor edge of v in shortest paths tree
  39. */
  40.  
  41. { 
  42.   node_array(bool) in_Q(G,false);
  43.   node_array(int)  count(G,0);
  44.  
  45.   int n = G.number_of_nodes();
  46.   b_queue(node) Q(n);
  47.  
  48.   node u,v;
  49.   edge e;
  50.   int c;
  51.  
  52.   forall_nodes(v,G) 
  53.     { pred[v] = 0;
  54.       dist[v] =  Infinity; 
  55.      }
  56.  
  57.   dist[s] = 0;
  58.   Q.append(s);
  59.   in_Q[s] = true;
  60.  
  61.   while (!Q.empty())
  62.     { u = Q.pop();
  63.       in_Q[u] = false;
  64.  
  65.       if (++count[u] > n) return false;
  66.  
  67.       forall_adj_edges(e,u) 
  68.         { v = target(e);
  69.           c = dist[u] + cost[e];
  70.  
  71.           if (c < dist[v]) 
  72.            { dist[v] = c; 
  73.              pred[v] = e;
  74.              if (!in_Q[v])  
  75.               { Q.append(v);
  76.                 in_Q[v]=true;
  77.                }
  78.  
  79.             }
  80.  
  81.          } /* forall */
  82.  
  83.      } // while
  84.  
  85.   return true;
  86.  
  87. }
  88.  
  89.  
  90.  
  91. #ifndef NO_REAL_GRAPH_ALG
  92.  
  93.  
  94. // BELLMAN_FORD for real valued edge costs:
  95.  
  96. bool BELLMAN_FORD(const graph& G, node s, const edge_array(real)& cost, 
  97.                                                 node_array(real)& dist, 
  98.                                                 node_array(edge)& pred ) 
  99.  
  100. { int n = G.number_of_nodes();
  101.   b_queue(node) Q(n);
  102.   node_array(bool) in_Q(G,false);
  103.   node_array(int) count(G,0);
  104.  
  105.   node u,v;
  106.   edge e;
  107.   real c;
  108.  
  109.   forall_nodes(v,G) 
  110.     { pred[v] = 0;
  111.       dist[v] =  Infinity; 
  112.      }
  113.  
  114.   dist[s] = 0;
  115.   Q.append(s);
  116.   in_Q[s] = true;
  117.  
  118.   while (!Q.empty())
  119.     { u = Q.pop();
  120.       in_Q[u] = false;
  121.  
  122.       if (++count[u] > n)  return false;
  123.  
  124.       forall_adj_edges(e,u) 
  125.         { v = target(e);
  126.           c = dist[u] + cost[e];
  127.  
  128.           if (c < dist[v]) 
  129.            { dist[v] = c; 
  130.              pred[v] = e;
  131.              if (!in_Q[v])  
  132.               { Q.append(v);
  133.                 in_Q[v] = true;
  134.                }
  135.  
  136.             }
  137.  
  138.          } /* forall */
  139.  
  140.      } // while
  141.  
  142.   return true;
  143.  
  144. }
  145.  
  146. #endif
  147.