COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/dijkstra.h @ 171:ec3d3596e3c9

Last change on this file since 171:ec3d3596e3c9 was 171:ec3d3596e3c9, checked in by Mihaly Barasz, 17 years ago

hurokeles bug

File size: 2.5 KB
RevLine 
[159]1// -*- C++ -*-
[170]2
3//ha predecessor az elejen nem invalid, akkor hagyd csak ugy
4//scanned mutatja hogy jo ertek van-e benne vagy szemet
5
[159]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
[170]31#ifndef DIJKSTRA_H
32#define DIJKSTRA_H
[159]33
34#include <fib_heap.h>
35
36namespace 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);
[167]78          heap.pop();
[159]79          distance.set(v, oldvalue);
[171]80          scanned.set(v,true);
[167]81
[159]82          OutEdgeIt e;
83          for( G.getFirst(e,v); G.valid(e); G.next(e)) {
[160]84            NodeIt w=G.bNode(e);
[159]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              } else if ( oldvalue+length.get(e) < heap.get(w) ) {
92                predecessor.set(w,e);
93                heap.decrease(w, oldvalue+length.get(e));
94              }
95            }
96          }
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      }
[167]115     
[159]116    };
[167]117 
[159]118}
119
120#endif
121
122
Note: See TracBrowser for help on using the repository browser.