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