[250] | 1 | /* |
---|
| 2 | Egy pontból összes többibe vezetõ legrövidebb utak irányított gráfban |
---|
| 3 | |
---|
| 4 | Preconditions: |
---|
| 5 | A gráf típus tud: |
---|
| 6 | - pontból kimenõ éleket sorban visszaadni |
---|
| 7 | A T számtípus, ami tud összehasonlítást, összedást |
---|
| 8 | A bemenetre: |
---|
| 9 | weight nemnegatív |
---|
| 10 | |
---|
| 11 | */ |
---|
| 12 | #ifndef DIJKSTRA_AT_H |
---|
| 13 | #define DIJKSTRA_AT_H |
---|
| 14 | |
---|
| 15 | |
---|
| 16 | |
---|
| 17 | //#include <algorithm> |
---|
| 18 | //#include <deque> |
---|
| 19 | //#include <vector> |
---|
| 20 | //#include "pf_hiba.hh" |
---|
| 21 | //#include <marci_list_graph.hh> |
---|
| 22 | //#include <marci_graph_traits.hh> |
---|
| 23 | |
---|
| 24 | |
---|
| 25 | using namespace std; |
---|
| 26 | |
---|
| 27 | namespace hugo { |
---|
| 28 | |
---|
| 29 | template <typename graph_type, typename T> |
---|
| 30 | class dijkstra_at { |
---|
| 31 | |
---|
| 32 | //Hasznos typedef-ek |
---|
| 33 | typedef typename graph_type::NodeIt NodeIt; |
---|
| 34 | typedef typename graph_type::EdgeIt EdgeIt; |
---|
| 35 | typedef typename graph_type::EachNodeIt EachNodeIt; |
---|
| 36 | typedef typename graph_type::EachEdgeIt EachEdgeIt; |
---|
| 37 | typedef typename graph_type::OutEdgeIt OutEdgeIt; |
---|
| 38 | typedef typename graph_type::InEdgeIt InEdgeIt; |
---|
| 39 | typedef typename graph_type::SymEdgeIt SymEdgeIt; |
---|
| 40 | |
---|
| 41 | |
---|
| 42 | |
---|
| 43 | //--------------------------------------------- |
---|
| 44 | //Parameters of the algorithm |
---|
| 45 | //--------------------------------------------- |
---|
| 46 | |
---|
| 47 | //--------------------------------------------- |
---|
| 48 | //Parameters of the algorithm |
---|
| 49 | //--------------------------------------------- |
---|
| 50 | |
---|
| 51 | private: |
---|
| 52 | //input |
---|
| 53 | graph_type& G; |
---|
| 54 | NodeIt s; |
---|
| 55 | typename graph_type::EdgeMap<T> &weight; |
---|
| 56 | //typename graph_type::EdgeMap<T> &capacity; |
---|
| 57 | //output |
---|
| 58 | //typename graph_type::EdgeMap<T> |
---|
| 59 | // typename graph_type::EdgeMap<T> preflow; |
---|
| 60 | |
---|
| 61 | //auxiliary variables for computation |
---|
| 62 | deque<NodeIt> next_to_reach; |
---|
| 63 | |
---|
| 64 | |
---|
| 65 | typename graph_type::NodeMap<bool> reached; |
---|
| 66 | |
---|
| 67 | //Variables holding output |
---|
| 68 | //Predessors in the shortest paths arborescence |
---|
| 69 | typename graph_type::NodeMap<NodeIt> pred; |
---|
| 70 | |
---|
| 71 | |
---|
| 72 | public: |
---|
| 73 | |
---|
| 74 | |
---|
| 75 | dijkstra_at( |
---|
| 76 | graph_type& _G, |
---|
| 77 | NodeIt _s, |
---|
| 78 | typename graph_type::EdgeMap<T> & _weight) |
---|
| 79 | : G(_G), s(_s), |
---|
| 80 | weight(_weight), |
---|
| 81 | next_to_reach(), |
---|
| 82 | reached(_G), |
---|
| 83 | pred(G) |
---|
| 84 | |
---|
| 85 | { |
---|
| 86 | } |
---|
| 87 | /*By Misi.*/ |
---|
| 88 | struct Node_dist_comp |
---|
| 89 | { |
---|
| 90 | NodeMap<graph_type, T> &d; |
---|
| 91 | Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} |
---|
| 92 | |
---|
| 93 | bool operator()(const NodeIt& u, const NodeIt& v) const |
---|
| 94 | { return d.get(u) < d.get(v); } |
---|
| 95 | }; |
---|
| 96 | |
---|
| 97 | |
---|
| 98 | |
---|
| 99 | void run() { |
---|
| 100 | |
---|
| 101 | NodeMap<graph_type, bool> scanned(G, false); |
---|
| 102 | std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> |
---|
| 103 | heap(( Node_dist_comp(distance) )); |
---|
| 104 | |
---|
| 105 | heap.push(s); |
---|
| 106 | reached.set(s, true); |
---|
| 107 | |
---|
| 108 | } |
---|
| 109 | |
---|
| 110 | |
---|
| 111 | }; |
---|
| 112 | |
---|
| 113 | |
---|
| 114 | |
---|
| 115 | |
---|
| 116 | |
---|
| 117 | |
---|
| 118 | }; //class dijkstra_at |
---|
| 119 | |
---|
| 120 | |
---|
| 121 | }//namespace hugo |
---|
| 122 | |
---|
| 123 | #endif //DIJKSTRA_AT |
---|