_bellman_ford.c

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

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



/*******************************************************************************
*                                                                              *
*  BELLMAN FORD                                                                *
*                                                                              *
*******************************************************************************/

#include <LEDA/graph_alg.h>
#include <LEDA/b_queue.h>


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



bool BELLMAN_FORD(const graph& G, node s, const num_edge_array& cost, 
                                                num_node_array& dist, 
                                                node_array<edge>& pred ) 

/* single source shortest paths from s using a queue (breadth first search)
   computes for all nodes v:
   a) dist[v] = cost of shortest path from s to v
   b) pred[v] = predecessor edge of v in shortest paths tree
*/

{ 
  num_node_array in_Q(G,false);
  num_node_array count(G,0);

  int n = G.number_of_nodes();

  b_queue<node> Q(n);

  node u,v;
  edge e;

  forall_nodes(v,G) 
  { pred[v] = 0;
    dist[v] =  MAXINT; 
   }

  dist[s] = 0;
  Q.append(s);
  in_Q[s] = true;

  while(! Q.empty() )
  { u = Q.pop();
    in_Q[u] = false;

    if (++count[u] > n) return false;   // negative cycle

    num_type du = dist[u];

    forall_adj_edges(e,u) 
    { v = target(e);
      num_type c = du + cost[e];

      if (c < dist[v]) 
      { dist[v] = c; 
        pred[v] = e;
        if (!in_Q[v])  
        { Q.append(v);
          in_Q[v]=true;
         }
       }
     } 
   }
  return true;
}