COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.h @ 159:0defa5aa1229

Last change on this file since 159:0defa5aa1229 was 159:0defa5aa1229, checked in by jacint, 16 years ago

* empty log message *

File size: 2.4 KB
Line 
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
37namespace 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.head(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
Note: See TracBrowser for help on using the repository browser.