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