/*******************************************************************************
+
+  LEDA 3.5
+
+  bellman_ford.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/


//------------------------------------------------------------------------------
// BELLMAN FORD                                                                
//                                                                              
// S. N"aher (1989)
//------------------------------------------------------------------------------


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


bool BELLMAN_FORD(const graph& G, node s, const edge_array<num_type>& cost, 
                                                node_array<num_type>& 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
*/

{ 
  node_array<int> count(G,0);

  int n = G.number_of_nodes();

  node_list Q;

  node u,v;
  edge e;

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

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

  while(! Q.empty() )
  { u = Q.pop();

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

    num_type du = dist[u];

    forall_adj_edges(e,u) 
    { v = G.opposite(u,e);              // makes it work for undirected graphs
      num_type c = du + cost[e];
      if (c < dist[v]) 
      { dist[v] = c; 
        pred[v] = e;
        if (!Q.member(v)) Q.append(v);
       }
     } 
   }
  return true;
}

