/* 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 //#include //#include //#include "pf_hiba.hh" //#include //#include using namespace std; namespace hugo { template 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 &weight; //typename graph_type::EdgeMap &capacity; //output //typename graph_type::EdgeMap // typename graph_type::EdgeMap preflow; //auxiliary variables for computation deque next_to_reach; typename graph_type::NodeMap reached; //Variables holding output //Predessors in the shortest paths arborescence typename graph_type::NodeMap pred; public: dijkstra_at( graph_type& _G, NodeIt _s, typename graph_type::EdgeMap & _weight) : G(_G), s(_s), weight(_weight), next_to_reach(), reached(_G), pred(G) { } /*By Misi.*/ struct Node_dist_comp { NodeMap &d; Node_dist_comp(NodeMap &_d) : d(_d) {} bool operator()(const NodeIt& u, const NodeIt& v) const { return d.get(u) < d.get(v); } }; void run() { NodeMap scanned(G, false); std::priority_queue, Node_dist_comp> heap(( Node_dist_comp(distance) )); heap.push(s); reached.set(s, true); } }; }; //class dijkstra_at }//namespace hugo #endif //DIJKSTRA_AT