1 | // -*- C++ -*- |
---|
2 | /* |
---|
3 | *template <Graph, T, Heap=FibHeap> |
---|
4 | * |
---|
5 | * |
---|
6 | *Constructor: |
---|
7 | * |
---|
8 | *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length) |
---|
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) : 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 | * |
---|
28 | *bool reach(NodeIt v) : true iff v is reachable from s |
---|
29 | * |
---|
30 | */ |
---|
31 | |
---|
32 | #ifndef DIJKSTRA_HH |
---|
33 | #define DIJKSTRA_HH |
---|
34 | |
---|
35 | #include <fib_heap.h> |
---|
36 | |
---|
37 | namespace hugo { |
---|
38 | |
---|
39 | template <typename Graph, typename T, |
---|
40 | typename Heap=FibHeap<typename Graph::NodeIt, T, |
---|
41 | typename Graph::NodeMap<int> > > |
---|
42 | class Dijkstra{ |
---|
43 | typedef typename Graph::NodeIt NodeIt; |
---|
44 | typedef typename Graph::EdgeIt EdgeIt; |
---|
45 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
46 | |
---|
47 | Graph& G; |
---|
48 | NodeIt s; |
---|
49 | typename Graph::NodeMap<EdgeIt> predecessor; |
---|
50 | typename Graph::NodeMap<T> distance; |
---|
51 | typename Graph::EdgeMap<T>& length; |
---|
52 | typename Graph::NodeMap<bool> reached; |
---|
53 | |
---|
54 | public : |
---|
55 | |
---|
56 | /* |
---|
57 | The distance of the nodes is 0. |
---|
58 | */ |
---|
59 | Dijkstra(Graph& _G, NodeIt const _s, |
---|
60 | typename Graph::EdgeMap<T>& _length) : |
---|
61 | G(_G), s(_s), predecessor(G), distance(G), |
---|
62 | length(_length), reached(G, false) { } |
---|
63 | |
---|
64 | |
---|
65 | void run() { |
---|
66 | |
---|
67 | typename Graph::NodeMap<bool> scanned(G, false); |
---|
68 | typename Graph::NodeMap<int> heap_map(G,-1); |
---|
69 | |
---|
70 | Heap heap(heap_map); |
---|
71 | |
---|
72 | heap.push(s,0); |
---|
73 | reached.set(s, true); |
---|
74 | |
---|
75 | while ( !heap.empty() ) { |
---|
76 | |
---|
77 | NodeIt v=heap.top(); |
---|
78 | T oldvalue=heap.get(v); |
---|
79 | distance.set(v, oldvalue); |
---|
80 | heap.pop(); |
---|
81 | |
---|
82 | OutEdgeIt e; |
---|
83 | for( G.getFirst(e,v); G.valid(e); G.next(e)) { |
---|
84 | NodeIt w=G.bNode(e); |
---|
85 | |
---|
86 | if ( !scanned.get(w) ) { |
---|
87 | if ( !reached.get(w) ) { |
---|
88 | reached.set(w,true); |
---|
89 | heap.push(w,oldvalue+length.get(e)); |
---|
90 | predecessor.set(w,e); |
---|
91 | |
---|
92 | } else if ( oldvalue+length.get(e) < heap.get(w) ) { |
---|
93 | predecessor.set(w,e); |
---|
94 | heap.decrease(w, oldvalue+length.get(e)); |
---|
95 | } |
---|
96 | } |
---|
97 | } |
---|
98 | scanned.set(v,true); |
---|
99 | } |
---|
100 | } |
---|
101 | |
---|
102 | |
---|
103 | T dist(NodeIt v) { |
---|
104 | return distance.get(v); |
---|
105 | } |
---|
106 | |
---|
107 | |
---|
108 | EdgeIt pred(NodeIt v) { |
---|
109 | if ( v!=s ) return predecessor.get(v); |
---|
110 | else return EdgeIt(); |
---|
111 | } |
---|
112 | |
---|
113 | |
---|
114 | bool reach(NodeIt v) { |
---|
115 | return reached.get(v); |
---|
116 | } |
---|
117 | |
---|
118 | }; |
---|
119 | |
---|
120 | } |
---|
121 | |
---|
122 | #endif |
---|
123 | |
---|
124 | |
---|