// -*- C++ -*-

//ha predecessor az elejen nem invalid, akkor hagyd csak ugy
//scanned mutatja hogy jo ertek van-e benne vagy szemet

/* 
 *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_H
#define DIJKSTRA_H

#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);
	  heap.pop();
	  distance.set(v, oldvalue);

	  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