lemon-0.x: src/work/athos/dijkstra

     1 /*

     2 Egy pontból összes többibe vezetõ legrövidebb utak irányított gráfban

     4 Preconditions:

     5 A gráf típus tud:

     6 - pontból kimenõ éleket sorban visszaadni

     7 A T számtípus, ami tud összehasonlítást, összedást

     8 A bemenetre:

     9 weight nemnegatív

    11 */

    12 #ifndef DIJKSTRA_AT_H

    13 #define DIJKSTRA_AT_H

    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>

    25 using namespace std;

    27 namespace hugo {

    29   template <typename graph_type, typename T>

    30   class dijkstra_at {

    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;

    43     //---------------------------------------------

    44     //Parameters of the algorithm

    45     //---------------------------------------------

    47     //---------------------------------------------

    48     //Parameters of the algorithm

    49     //---------------------------------------------

    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;

    61     //auxiliary variables for computation

    62     deque<NodeIt> next_to_reach;

    65     typename graph_type::NodeMap<bool> reached;

    67     //Variables holding output

    68     //Predessors in the shortest paths arborescence

    69     typename graph_type::NodeMap<NodeIt> pred;

    72   public:

    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)

    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) {}

    93 	bool operator()(const NodeIt& u, const NodeIt& v) const

    94 	{ return d.get(u) < d.get(v); }

    95       };

    99       void run() {

   101 	NodeMap<graph_type, bool> scanned(G, false);

   102 	std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp>

   103 	  heap(( Node_dist_comp(distance) ));

   105 	heap.push(s);

   106 	reached.set(s, true);

   108       }

   111     };

   118   };  //class dijkstra_at

   121 }//namespace hugo

   123 #endif //DIJKSTRA_AT

author	klao
	Thu, 29 Apr 2004 23:24:42 +0000
changeset 490	ceb56ff9d07f
child 921	818510fa3d99
permissions	-rw-r--r--