source:lemon-0.x/src/work/jacint/dijkstra.hh@95:3322fbf254d2

Last change on this file since 95:3322fbf254d2 was 78:ecc1171307be, checked in by jacint, 20 years ago

modern valtozat

File size: 3.6 KB
Line
1/*
2 *dijkstra
3 *by jacint
4 *Performs Dijkstra's algorithm from Node s.
5 *
6 *Constructor:
7 *
8 *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)
9 *
10 *
11 *
12 *Member functions:
13 *
14 *void run()
15 *
16 *  The following function should be used after run() was already run.
17 *
18 *
19 *T dist(NodeIt v) : returns the distance from s to v.
20 *   It is 0 if v is not reachable from s.
21 *
22 *
23 *EdgeIt pred(NodeIt v)
24 *   Returns the last Edge of a shortest s-v path.
25 *   Returns an invalid iterator if v=s or v is not
26 *   reachable from s.
27 *
28 *
29 *bool reach(NodeIt v) : true if v is reachable from s
30 *
31 *
32 *
33 *
34 *
35 *Problems:
36 *
37 *Heap implementation is needed, because the priority queue of stl
38 *does not have a mathod for key-decrease, so we had to use here a
39 *g\'any solution.
40 *
41 *The implementation of infinity would be desirable, see after line 100.
42 */
43
44#ifndef DIJKSTRA_HH
45#define DIJKSTRA_HH
46
47#include <queue>
48#include <algorithm>
49
50#include <marci_graph_traits.hh>
51#include <marciMap.hh>
52
53
54namespace std {
55  namespace marci {
56
57
58
59
60
61    template <typename graph_type, typename T>
62    class dijkstra{
63      typedef typename graph_traits<graph_type>::NodeIt NodeIt;
64      typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
65      typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
66      typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
67      typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;
68
69
70      graph_type& G;
71      NodeIt s;
72      NodeMap<graph_type, EdgeIt> predecessor;
73      NodeMap<graph_type, T> distance;
74      EdgeMap<graph_type, T> length;
75      NodeMap<graph_type, bool> reached;
76
77  public :
78
79    /*
80      The distance of all the Nodes is 0.
81    */
82    dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) :
83      G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
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.put(s, true);
107
108        while (!heap.empty()) {
109
110          NodeIt v=heap.top();
111          heap.pop();
112
113
114          if (!scanned.get(v)) {
115
116            for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
118
119              if (!scanned.get(w)) {
120                if (!reached.get(w)) {
121                  reached.put(w,true);
122                  distance.put(w, distance.get(v)-length.get(e));
123                  predecessor.put(w,e);
124                } else if (distance.get(v)-length.get(e)>distance.get(w)) {
125                  distance.put(w, distance.get(v)-length.get(e));
126                  predecessor.put(w,e);
127                }
128
129                heap.push(w);
130
131              }
132
133            }
134            scanned.put(v,true);
135
136          } // if (!scanned.get(v))
137
138
139
140        } // while (!heap.empty())
141
142
143      } //void run()
144
145
146
147
148
149      /*
150       *Returns the distance of the Node v.
151       *It is 0 for the root and for the Nodes not
152       *reachable form the root.
153       */
154      T dist(NodeIt v) {
155        return -distance.get(v);
156      }
157
158
159
160      /*
161       *  Returns the last Edge of a shortest s-v path.
162       *  Returns an invalid iterator if v=root or v is not
163       *  reachable from the root.
164       */
165      EdgeIt pred(NodeIt v) {
166        if (v!=s) { return predecessor.get(v);}
167        else {return EdgeIt();}
168      }
169
170
171
172      bool reach(NodeIt v) {
173        return reached.get(v);
174      }
175
176
177
178
179
180
181
182
183
184    };// class dijkstra
185
186
187
188  } // namespace marci
189}
190#endif //DIJKSTRA_HH
191
192
Note: See TracBrowser for help on using the repository browser.