// -*- C++ -*-

 /* 

  *template <Graph, T, Heap=FibHeap>

  *

  *

  *Constructor: 

  *

  *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)

  *

  *

  *

  *Member functions:

  *

  *void run()

  *

  *  The following function should be used after run() was already run.

  *

  *

  *T dist(NodeIt v) : returns the distance from s to v. 

  *   It is 0 if v is not reachable from s.

  *

  *

  *EdgeIt pred(NodeIt v) : returns the last edge 

  *   of a shortest s-v path. Returns an invalid iterator 

  *   if v=s or v is not reachable from s.

  *

  *

  *bool reach(NodeIt v) : true iff v is reachable from s

  *

  */

 #ifndef DIJKSTRA_HH

 #define DIJKSTRA_HH

 #include <fib_heap.h>

 namespace hugo {

   template <typename Graph, typename T, 

     typename Heap=FibHeap<typename Graph::NodeIt, T, 

     typename Graph::NodeMap<int> > >

     class Dijkstra{

       typedef typename Graph::NodeIt NodeIt;

       typedef typename Graph::EdgeIt EdgeIt;

       typedef typename Graph::OutEdgeIt OutEdgeIt;

       Graph& G;

       NodeIt s;

       typename Graph::NodeMap<EdgeIt> predecessor;

       typename Graph::NodeMap<T> distance;

       typename Graph::EdgeMap<T>& length;

       typename Graph::NodeMap<bool> reached;

   public :

     /*

       The distance of the nodes is 0.

     */

     Dijkstra(Graph& _G, NodeIt const _s, 

 	     typename Graph::EdgeMap<T>& _length) : 

       G(_G), s(_s), predecessor(G), distance(G), 

       length(_length), reached(G, false) { }

       void run() {

 	typename Graph::NodeMap<bool> scanned(G, false);

 	typename Graph::NodeMap<int> heap_map(G,-1);

 	Heap heap(heap_map);

 	heap.push(s,0); 

 	reached.set(s, true);

 	while ( !heap.empty() ) {

 	  NodeIt v=heap.top(); 

 	  T oldvalue=heap.get(v);

 	  distance.set(v, oldvalue);

 	  heap.pop();

 	  OutEdgeIt e;

 	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {

 	    NodeIt w=G.bNode(e); 

 	    if ( !scanned.get(w) ) {

 	      if ( !reached.get(w) ) {

 		reached.set(w,true);

 		heap.push(w,oldvalue+length.get(e)); 

 		predecessor.set(w,e);

 	      } else if ( oldvalue+length.get(e) < heap.get(w) ) {

 		predecessor.set(w,e);

 		heap.decrease(w, oldvalue+length.get(e)); 

 	      }

 	    }

 	  }

 	  scanned.set(v,true);

 	}

       } 

       T dist(NodeIt v) {

 	return distance.get(v);

       }

       EdgeIt pred(NodeIt v) {

 	if ( v!=s ) return predecessor.get(v);

 	else return EdgeIt();

       }

       bool reach(NodeIt v) {

 	return reached.get(v);

       }

     };

 }

 #endif