source:lemon-0.x/src/work/athos/dijkstra_at.h@650:588ff2ca55bd

Last change on this file since 650:588ff2ca55bd was 250:81a3d0abe5f3, checked in by athos, 19 years ago

Hozzáadtam pár dolgot, mielőtt áttérünk az svn-re.

File size: 2.5 KB
Line
1/*
2Egy pontból összes többibe vezetõ legrövidebb utak irányított gráfban
3
4Preconditions:
5A gráf típus tud:
6- pontból kimenõ éleket sorban visszaadni
7A T számtípus, ami tud összehasonlítást, összedást
8A bemenetre:
9weight nemnegatív
10
11*/
12#ifndef DIJKSTRA_AT_H
13#define DIJKSTRA_AT_H
14
15
16
17//#include <algorithm>
18//#include <deque>
19//#include <vector>
20//#include "pf_hiba.hh"
21//#include <marci_list_graph.hh>
22//#include <marci_graph_traits.hh>
23
24
25using namespace std;
26
27namespace hugo {
28
29  template <typename graph_type, typename T>
30  class dijkstra_at {
31
32    //Hasznos typedef-ek
33    typedef typename graph_type::NodeIt NodeIt;
34    typedef typename graph_type::EdgeIt EdgeIt;
35    typedef typename graph_type::EachNodeIt EachNodeIt;
36    typedef typename graph_type::EachEdgeIt EachEdgeIt;
37    typedef typename graph_type::OutEdgeIt OutEdgeIt;
38    typedef typename graph_type::InEdgeIt InEdgeIt;
39    typedef typename graph_type::SymEdgeIt SymEdgeIt;
40
41
42
43    //---------------------------------------------
44    //Parameters of the algorithm
45    //---------------------------------------------
46
47    //---------------------------------------------
48    //Parameters of the algorithm
49    //---------------------------------------------
50
51  private:
52    //input
53    graph_type& G;
54    NodeIt s;
55    typename graph_type::EdgeMap<T> &weight;
56    //typename graph_type::EdgeMap<T>  &capacity;
57    //output
58    //typename graph_type::EdgeMap<T>
59    //    typename graph_type::EdgeMap<T> preflow;
60
61    //auxiliary variables for computation
62    deque<NodeIt> next_to_reach;
63
64
65    typename graph_type::NodeMap<bool> reached;
66
67    //Variables holding output
68    //Predessors in the shortest paths arborescence
69    typename graph_type::NodeMap<NodeIt> pred;
70
71
72  public:
73
74
75    dijkstra_at(
76                      graph_type& _G,
77                      NodeIt _s,
78                      typename graph_type::EdgeMap<T> & _weight)
79      : G(_G), s(_s),
80      weight(_weight),
81      next_to_reach(),
82      reached(_G),
83      pred(G)
84
85    {
86    }
87      /*By Misi.*/
88      struct Node_dist_comp
89      {
90        NodeMap<graph_type, T> &d;
91        Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {}
92
93        bool operator()(const NodeIt& u, const NodeIt& v) const
94        { return d.get(u) < d.get(v); }
95      };
96
97
98
99      void run() {
100
101        NodeMap<graph_type, bool> scanned(G, false);
102        std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp>
103          heap(( Node_dist_comp(distance) ));
104
105        heap.push(s);
106        reached.set(s, true);
107
108      }
109
110
111    };
112
113
114
115
116
117
118  };  //class dijkstra_at
119
120
121}//namespace hugo
122
123#endif //DIJKSTRA_AT
Note: See TracBrowser for help on using the repository browser.