COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.h @ 167:7949a29a334e

Last change on this file since 167:7949a29a334e was 167:7949a29a334e, checked in by jacint, 17 years ago

* empty log message *

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