jacint@159: // -*- C++ -*-
jacint@170: 
jacint@170: //ha predecessor az elejen nem invalid, akkor hagyd csak ugy
jacint@170: //scanned mutatja hogy jo ertek van-e benne vagy szemet
jacint@170: 
jacint@159: /* 
jacint@159:  *template <Graph, T, Heap=FibHeap>
jacint@159:  *
jacint@159:  *Constructor: 
jacint@159:  *
jacint@159:  *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
jacint@159:  *
jacint@159:  *
jacint@159:  *Member functions:
jacint@159:  *
jacint@159:  *void run()
jacint@159:  *
jacint@159:  *  The following function should be used after run() was already run.
jacint@159:  *
jacint@159:  *T dist(NodeIt v) : returns the distance from s to v. 
jacint@159:  *   It is 0 if v is not reachable from s.
jacint@159:  *
jacint@159:  *EdgeIt pred(NodeIt v) : returns the last edge 
jacint@159:  *   of a shortest s-v path. Returns an invalid iterator 
jacint@159:  *   if v=s or v is not reachable from s.
jacint@159:  *
jacint@159:  *bool reach(NodeIt v) : true iff v is reachable from s
jacint@159:  *
jacint@159:  */
jacint@159: 
jacint@170: #ifndef DIJKSTRA_H
jacint@170: #define DIJKSTRA_H
jacint@159: 
jacint@159: #include <fib_heap.h>
jacint@159: 
jacint@159: namespace hugo {
jacint@159: 
jacint@159:   template <typename Graph, typename T, 
jacint@159:     typename Heap=FibHeap<typename Graph::NodeIt, T, 
jacint@159:     typename Graph::NodeMap<int> > >
jacint@159:     class Dijkstra{
jacint@159:       typedef typename Graph::NodeIt NodeIt;
jacint@159:       typedef typename Graph::EdgeIt EdgeIt;
jacint@159:       typedef typename Graph::OutEdgeIt OutEdgeIt;
jacint@159:       
jacint@159:       Graph& G;
jacint@159:       NodeIt s;
jacint@159:       typename Graph::NodeMap<EdgeIt> predecessor;
jacint@159:       typename Graph::NodeMap<T> distance;
jacint@159:       typename Graph::EdgeMap<T>& length;
jacint@159:       typename Graph::NodeMap<bool> reached;
jacint@159:           
jacint@159:   public :
jacint@159: 
jacint@159:     /*
jacint@159:       The distance of the nodes is 0.
jacint@159:     */
jacint@159:     Dijkstra(Graph& _G, NodeIt const _s, 
jacint@159: 	     typename Graph::EdgeMap<T>& _length) : 
jacint@159:       G(_G), s(_s), predecessor(G), distance(G), 
jacint@159:       length(_length), reached(G, false) { }
jacint@159:     
jacint@159:       
jacint@159:       void run() {
jacint@159: 	
jacint@159: 	typename Graph::NodeMap<bool> scanned(G, false);
jacint@159: 	typename Graph::NodeMap<int> heap_map(G,-1);
jacint@159: 
jacint@159: 	Heap heap(heap_map);
jacint@159: 
jacint@159: 	heap.push(s,0); 
jacint@159: 	reached.set(s, true);
jacint@159: 
jacint@159: 	while ( !heap.empty() ) {
jacint@159: 
jacint@159: 	  NodeIt v=heap.top(); 
jacint@159: 	  T oldvalue=heap.get(v);
jacint@167: 	  heap.pop();
jacint@159: 	  distance.set(v, oldvalue);
klao@171: 	  scanned.set(v,true);
jacint@167: 
jacint@159: 	  OutEdgeIt e;
jacint@159: 	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
jacint@160: 	    NodeIt w=G.bNode(e); 
jacint@159: 	    
jacint@159: 	    if ( !scanned.get(w) ) {
jacint@159: 	      if ( !reached.get(w) ) {
jacint@159: 		reached.set(w,true);
jacint@159: 		heap.push(w,oldvalue+length.get(e)); 
jacint@159: 		predecessor.set(w,e);
jacint@159: 	      } else if ( oldvalue+length.get(e) < heap.get(w) ) {
jacint@159: 		predecessor.set(w,e);
jacint@159: 		heap.decrease(w, oldvalue+length.get(e)); 
jacint@159: 	      }
jacint@159: 	    }
jacint@159: 	  }
jacint@159: 	}
jacint@159:       } 
jacint@159:       
jacint@159: 
jacint@159:       T dist(NodeIt v) {
jacint@159: 	return distance.get(v);
jacint@159:       }
jacint@159: 
jacint@159: 
jacint@159:       EdgeIt pred(NodeIt v) {
jacint@159: 	if ( v!=s ) return predecessor.get(v);
jacint@159: 	else return EdgeIt();
jacint@159:       }
jacint@159:      
jacint@159: 
jacint@159:       bool reach(NodeIt v) {
jacint@159: 	return reached.get(v);
jacint@159:       }
jacint@167:       
jacint@159:     };
jacint@167:   
jacint@159: }
jacint@159: 
jacint@159: #endif
jacint@159: 
jacint@159: