// -*- 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