/*******************************************************************************
+
+  LEDA 3.5
+
+  moore.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.
+ 
*******************************************************************************/
//------------------------------------------------------------------------------
// MOORE  (single source shortest paths)
//
// S. N"aher (last modification: 1996)
//------------------------------------------------------------------------------
 
#include <LEDA/graph_alg.h>

void  MOORE(const graph& g, node s, const edge_array<num_type>& cost,
                                         node_array<num_type>& dist, node t) 
{
  // use a double ended queue of candidate nodes (node_list)
  // and a node_array<num_type> for dist values
  // stop when t reached (if t != nil)

  dist.init(g,max_num); // initialize labels
  dist[s] = 0;

  node_list labeled;  // deque of candidate nodes
  labeled.append(s);

  while (! labeled.empty()) 
  { 
    node v = labeled.pop();
    num_type dv = dist[v];

    if (t && dv > dist[t]) continue;

    edge e;
    forall_adj_edges(e,v)
    { node w = g.opposite(v,e);
      num_type d = dv + cost[e];
      if (d < dist[w]) 
      { if ( ! labeled(w) ) 
        { if (dist[w] == max_num)
	       labeled.append(w);
	    else
	       labeled.push(w);
	   }
	  dist[w] = d;
       }
     }
  }
}

