/*

 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 lemon {

   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 lemon

 #endif //DIJKSTRA_AT