home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _all_pai.c next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.6 KB  |  115 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _all_pairs.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. *  ALL PAIRS SHORTEST PATHS                                                    *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25.  
  26. void ALL_PAIRS_SHORTEST_PATHS(graph&G, const edge_array(int)& cost, 
  27.                                              node_matrix(int)& DIST)
  28. { 
  29.   // computes for every node pair (v,w) DIST(v,w) = cost of the least cost
  30.   // path from v to w, the single source shortest paths algorithms BELLMAN_FORD
  31.   // and DIJKSTRA are used as subroutines
  32.  
  33.   edge e;
  34.   node v,w;
  35.  
  36.   int C = 0;
  37.   forall_edges(e,G)  C += ((cost[e]>0) ? cost[e] : -cost[e]);
  38.  
  39.   node s = G.new_node();
  40.   forall_nodes(v,G) G.new_edge(s,v);
  41.  
  42.   edge_array(int) cost1(G);
  43.   node_array(int) dist1(G);
  44.  
  45.   node_array(edge)  pred(G);
  46.  
  47.   forall_edges(e,G)  
  48.     if (source(e)==s) cost1[e] = C;
  49.     else cost1[e] =  cost[e];
  50.  
  51.   BELLMAN_FORD(G,s,cost1,dist1,pred);
  52.  
  53.   G.del_node(s);
  54.  
  55.   forall_edges(e,G) cost1[e] = dist1[source(e)] + cost[e] - dist1[target(e)];
  56.  
  57.   forall_nodes(v,G) DIJKSTRA(G,v,cost1,DIST[v],pred);
  58.  
  59.   forall_nodes(v,G)
  60.     forall_nodes(w,G)
  61.       { int d = dist1[w] - dist1[v];
  62.         DIST(v,w) += d;
  63.        }
  64.  
  65. }
  66.  
  67.  
  68.  
  69. #ifndef NO_REAL_GRAPH_ALG
  70.  
  71. // For real valued edge costs:
  72.  
  73. void ALL_PAIRS_SHORTEST_PATHS(graph&G, const edge_array(real)& cost, 
  74.                                              node_matrix(real)& DIST)
  75. { 
  76.  
  77.   edge e;
  78.   node v,w;
  79.   real C = 0;
  80.  
  81.   forall_edges(e,G) 
  82.    if (cost[e]>0) C += cost[e];
  83.    else  C -= cost[e];
  84.  
  85.   node s = G.new_node();
  86.   forall_nodes(v,G) G.new_edge(s,v);
  87.  
  88.   edge_array(real) cost1(G);
  89.   node_array(real) dist1(G);
  90.  
  91.   node_array(edge)  pred(G);
  92.  
  93.   forall_edges(e,G)  
  94.     if (source(e)==s) cost1[e] = C;
  95.     else cost1[e] =  cost[e];
  96.  
  97.   BELLMAN_FORD(G,s,cost1,dist1,pred);
  98.  
  99.   G.del_node(s);
  100.  
  101.   forall_edges(e,G) cost1[e] = dist1[source(e)] + cost[e] - dist1[target(e)];
  102.  
  103.   forall_nodes(v,G) DIJKSTRA(G,v,cost1,DIST[v],pred);
  104.  
  105.   forall_nodes(v,G)
  106.     forall_nodes(w,G)
  107.       { real d = dist1[w] - dist1[v];
  108.         DIST(v,w) += d;
  109.        }
  110. }
  111.  
  112.  
  113.  
  114. #endif
  115.