athos@250: /*
athos@250: Egy pontból összes többibe vezető legrövidebb utak irányított gráfban
athos@250: 
athos@250: Preconditions:
athos@250: A gráf típus tud:
athos@250: - pontból kimenő éleket sorban visszaadni
athos@250: A T számtípus, ami tud összehasonlítást, összedást
athos@250: A bemenetre:
athos@250: weight nemnegatív
athos@250: 
athos@250: */
athos@250: #ifndef DIJKSTRA_AT_H
athos@250: #define DIJKSTRA_AT_H
athos@250: 
athos@250: 
athos@250: 
athos@250: //#include <algorithm>
athos@250: //#include <deque>
athos@250: //#include <vector>
athos@250: //#include "pf_hiba.hh"
athos@250: //#include <marci_list_graph.hh>
athos@250: //#include <marci_graph_traits.hh>
athos@250: 
athos@250: 
athos@250: using namespace std;
athos@250: 
athos@250: namespace hugo {
athos@250: 
athos@250:   template <typename graph_type, typename T>
athos@250:   class dijkstra_at {
athos@250: 
athos@250:     //Hasznos typedef-ek
athos@250:     typedef typename graph_type::NodeIt NodeIt;
athos@250:     typedef typename graph_type::EdgeIt EdgeIt;
athos@250:     typedef typename graph_type::EachNodeIt EachNodeIt;
athos@250:     typedef typename graph_type::EachEdgeIt EachEdgeIt;
athos@250:     typedef typename graph_type::OutEdgeIt OutEdgeIt;
athos@250:     typedef typename graph_type::InEdgeIt InEdgeIt;
athos@250:     typedef typename graph_type::SymEdgeIt SymEdgeIt;
athos@250: 
athos@250: 
athos@250: 
athos@250:     //---------------------------------------------
athos@250:     //Parameters of the algorithm
athos@250:     //---------------------------------------------
athos@250: 
athos@250:     //---------------------------------------------
athos@250:     //Parameters of the algorithm
athos@250:     //---------------------------------------------
athos@250:  
athos@250:   private:
athos@250:     //input
athos@250:     graph_type& G;
athos@250:     NodeIt s;
athos@250:     typename graph_type::EdgeMap<T> &weight;
athos@250:     //typename graph_type::EdgeMap<T>  &capacity;
athos@250:     //output
athos@250:     //typename graph_type::EdgeMap<T>  
athos@250:     //    typename graph_type::EdgeMap<T> preflow;
athos@250:       
athos@250:     //auxiliary variables for computation
athos@250:     deque<NodeIt> next_to_reach;
athos@250:     
athos@250:     
athos@250:     typename graph_type::NodeMap<bool> reached;
athos@250: 
athos@250:     //Variables holding output
athos@250:     //Predessors in the shortest paths arborescence
athos@250:     typename graph_type::NodeMap<NodeIt> pred;
athos@250: 
athos@250: 
athos@250:   public:
athos@250:   
athos@250: 
athos@250:     dijkstra_at(
athos@250: 		      graph_type& _G, 
athos@250: 		      NodeIt _s, 
athos@250: 		      typename graph_type::EdgeMap<T> & _weight)
athos@250:       : G(_G), s(_s),
athos@250:       weight(_weight),
athos@250:       next_to_reach(),
athos@250:       reached(_G),
athos@250:       pred(G)
athos@250:      	
athos@250:     { 
athos@250:     }
athos@250:       /*By Misi.*/
athos@250:       struct Node_dist_comp
athos@250:       {
athos@250: 	NodeMap<graph_type, T> &d;
athos@250: 	Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 
athos@250: 	
athos@250: 	bool operator()(const NodeIt& u, const NodeIt& v) const 
athos@250: 	{ return d.get(u) < d.get(v); }
athos@250:       };
athos@250: 
athos@250: 
athos@250:       
athos@250:       void run() {
athos@250: 	
athos@250: 	NodeMap<graph_type, bool> scanned(G, false);
athos@250: 	std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 
athos@250: 	  heap(( Node_dist_comp(distance) ));
athos@250: 	
athos@250: 	heap.push(s);
athos@250: 	reached.set(s, true);
athos@250: 	
athos@250:       }
athos@250: 
athos@250:       
athos@250:     };
athos@250:   
athos@250: 
athos@250: 
athos@250: 
athos@250: 
athos@250:  
athos@250:   };  //class dijkstra_at  
athos@250: 
athos@250: 
athos@250: }//namespace hugo
athos@250: 
athos@250: #endif //DIJKSTRA_AT