source: lemon-0.x/src/work/jacint/dijkstra.h @ 170:9091b1ebca27

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