1 | // -*- C++ -*- |
---|
2 | |
---|
3 | //ha predecessor az elejen nem invalid, akkor hagyd csak ugy |
---|
4 | //scanned mutatja hogy jo ertek van-e benne vagy szemet |
---|
5 | |
---|
6 | /* |
---|
7 | *template <Graph, T, Heap=FibHeap> |
---|
8 | * |
---|
9 | *Constructor: |
---|
10 | * |
---|
11 | *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length) |
---|
12 | * |
---|
13 | * |
---|
14 | *Member functions: |
---|
15 | * |
---|
16 | *void run() |
---|
17 | * |
---|
18 | * The following function should be used after run() was already run. |
---|
19 | * |
---|
20 | *T dist(NodeIt v) : returns the distance from s to v. |
---|
21 | * It is 0 if v is not reachable from s. |
---|
22 | * |
---|
23 | *EdgeIt pred(NodeIt v) : returns the last edge |
---|
24 | * of a shortest s-v path. Returns an invalid iterator |
---|
25 | * if v=s or v is not reachable from s. |
---|
26 | * |
---|
27 | *bool reach(NodeIt v) : true iff v is reachable from s |
---|
28 | * |
---|
29 | */ |
---|
30 | |
---|
31 | #ifndef DIJKSTRA_H |
---|
32 | #define DIJKSTRA_H |
---|
33 | |
---|
34 | #include <fib_heap.h> |
---|
35 | |
---|
36 | namespace hugo { |
---|
37 | |
---|
38 | template <typename Graph, typename T, |
---|
39 | typename Heap=FibHeap<typename Graph::NodeIt, T, |
---|
40 | typename Graph::NodeMap<int> > > |
---|
41 | class Dijkstra{ |
---|
42 | typedef typename Graph::NodeIt NodeIt; |
---|
43 | typedef typename Graph::EdgeIt EdgeIt; |
---|
44 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
45 | |
---|
46 | Graph& G; |
---|
47 | NodeIt s; |
---|
48 | typename Graph::NodeMap<EdgeIt> predecessor; |
---|
49 | typename Graph::NodeMap<T> distance; |
---|
50 | typename Graph::EdgeMap<T>& length; |
---|
51 | typename Graph::NodeMap<bool> reached; |
---|
52 | |
---|
53 | public : |
---|
54 | |
---|
55 | /* |
---|
56 | The distance of the nodes is 0. |
---|
57 | */ |
---|
58 | Dijkstra(Graph& _G, NodeIt const _s, |
---|
59 | typename Graph::EdgeMap<T>& _length) : |
---|
60 | G(_G), s(_s), predecessor(G), distance(G), |
---|
61 | length(_length), reached(G, false) { } |
---|
62 | |
---|
63 | |
---|
64 | void run() { |
---|
65 | |
---|
66 | typename Graph::NodeMap<bool> scanned(G, false); |
---|
67 | typename Graph::NodeMap<int> heap_map(G,-1); |
---|
68 | |
---|
69 | Heap heap(heap_map); |
---|
70 | |
---|
71 | heap.push(s,0); |
---|
72 | reached.set(s, true); |
---|
73 | |
---|
74 | while ( !heap.empty() ) { |
---|
75 | |
---|
76 | NodeIt v=heap.top(); |
---|
77 | T oldvalue=heap.get(v); |
---|
78 | heap.pop(); |
---|
79 | distance.set(v, oldvalue); |
---|
80 | |
---|
81 | OutEdgeIt e; |
---|
82 | for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
---|
83 | NodeIt w=G.bNode(e); |
---|
84 | |
---|
85 | if ( !scanned.get(w) ) { |
---|
86 | if ( !reached.get(w) ) { |
---|
87 | reached.set(w,true); |
---|
88 | heap.push(w,oldvalue+length.get(e)); |
---|
89 | predecessor.set(w,e); |
---|
90 | } else if ( oldvalue+length.get(e) < heap.get(w) ) { |
---|
91 | predecessor.set(w,e); |
---|
92 | heap.decrease(w, oldvalue+length.get(e)); |
---|
93 | } |
---|
94 | } |
---|
95 | } |
---|
96 | scanned.set(v,true); |
---|
97 | } |
---|
98 | } |
---|
99 | |
---|
100 | |
---|
101 | T dist(NodeIt v) { |
---|
102 | return distance.get(v); |
---|
103 | } |
---|
104 | |
---|
105 | |
---|
106 | EdgeIt pred(NodeIt v) { |
---|
107 | if ( v!=s ) return predecessor.get(v); |
---|
108 | else return EdgeIt(); |
---|
109 | } |
---|
110 | |
---|
111 | |
---|
112 | bool reach(NodeIt v) { |
---|
113 | return reached.get(v); |
---|
114 | } |
---|
115 | |
---|
116 | }; |
---|
117 | |
---|
118 | } |
---|
119 | |
---|
120 | #endif |
---|
121 | |
---|
122 | |
---|