/*

Egy pontból összes többibe vezetõ legrövidebb utak irányított gráfban

Preconditions:

A gráf típus tud:

- pontból kimenõ éleket sorban visszaadni

A T számtípus, ami tud összehasonlítást, összedást

A bemenetre:

weight nemnegatív

*/

#ifndef DIJKSTRA_AT_H

#define DIJKSTRA_AT_H

//#include <algorithm>

//#include <deque>

//#include <vector>

//#include "pf_hiba.hh"

//#include <marci_list_graph.hh>

//#include <marci_graph_traits.hh>

using namespace std;

namespace hugo {

  template <typename graph_type, typename T>

  class dijkstra_at {

    //Hasznos typedef-ek

    typedef typename graph_type::NodeIt NodeIt;

    typedef typename graph_type::EdgeIt EdgeIt;

    typedef typename graph_type::EachNodeIt EachNodeIt;

    typedef typename graph_type::EachEdgeIt EachEdgeIt;

    typedef typename graph_type::OutEdgeIt OutEdgeIt;

    typedef typename graph_type::InEdgeIt InEdgeIt;

    typedef typename graph_type::SymEdgeIt SymEdgeIt;

    //---------------------------------------------

    //Parameters of the algorithm

    //---------------------------------------------

    //---------------------------------------------

    //Parameters of the algorithm

    //---------------------------------------------

  private:

    //input

    graph_type& G;

    NodeIt s;

    typename graph_type::EdgeMap<T> &weight;

    //typename graph_type::EdgeMap<T>  &capacity;

    //output

    //typename graph_type::EdgeMap<T>  

    //    typename graph_type::EdgeMap<T> preflow;

    //auxiliary variables for computation

    deque<NodeIt> next_to_reach;

    typename graph_type::NodeMap<bool> reached;

    //Variables holding output

    //Predessors in the shortest paths arborescence

    typename graph_type::NodeMap<NodeIt> pred;

  public:

    dijkstra_at(

		      graph_type& _G, 

		      NodeIt _s, 

		      typename graph_type::EdgeMap<T> & _weight)

      : G(_G), s(_s),

      weight(_weight),

      next_to_reach(),

      reached(_G),

      pred(G)

    { 

    }

      /*By Misi.*/

      struct Node_dist_comp

      {

	NodeMap<graph_type, T> &d;

	Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 

	bool operator()(const NodeIt& u, const NodeIt& v) const 

	{ return d.get(u) < d.get(v); }

      };

      void run() {

	NodeMap<graph_type, bool> scanned(G, false);

	std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 

	  heap(( Node_dist_comp(distance) ));

	heap.push(s);

	reached.set(s, true);

      }

    };

  };  //class dijkstra_at  

}//namespace hugo

#endif //DIJKSTRA_AT