_all_pairs.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _all_pairs.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/



/*******************************************************************************
*                                                                              *
*  ALL PAIRS SHORTEST PATHS                                                    *
*                                                                              *
*******************************************************************************/

#include <LEDA/graph_alg.h>

#if defined(REAL_NUMBERS)
typedef double num_type;
typedef node_array<double> num_node_array;
typedef edge_array<double> num_edge_array;
typedef node_matrix<double> num_node_matrix;
#else
typedef int num_type;
typedef node_array<int> num_node_array;
typedef edge_array<int> num_edge_array;
typedef node_matrix<int> num_node_matrix;
#endif


void ALL_PAIRS_SHORTEST_PATHS(graph&G, const num_edge_array& cost, 
                                             num_node_matrix& DIST)
{ 
  // computes for every node pair (v,w) DIST(v,w) = cost of the least cost
  // path from v to w, the single source shortest paths algorithms BELLMAN_FORD
  // and DIJKSTRA are used as subroutines

  edge e;
  node v,w;

  num_type C = 0;
  forall_edges(e,G)  C += ((cost[e]>0) ? cost[e] : -cost[e]);

  node s = G.new_node();
  forall_nodes(v,G) G.new_edge(s,v);

  num_edge_array cost1(G);
  num_node_array dist1(G);

  node_array<edge>  pred(G);

  forall_edges(e,G)  
    if (source(e)==s) cost1[e] = C;
    else cost1[e] =  cost[e];

  BELLMAN_FORD(G,s,cost1,dist1,pred);

  G.del_node(s);

  forall_edges(e,G) cost1[e] = dist1[source(e)] + cost[e] - dist1[target(e)];


  // (G,cost1) is a non-negative network
  // for every node v compute row DIST[v] of the distance matrix  DIST 
  // by a call of DIJKSTRA(G,v,cost1,DIST[v])

  forall_nodes(v,G) DIJKSTRA(G,v,cost1,DIST[v],pred);


  // correct the entries of DIST

  forall_nodes(v,G)
  { num_type dv = dist1[v];
    forall_nodes(w,G) DIST(v,w) += (dist1[w] - dv);
   }

}