Changeset 373:259ea2d741a2 in lemon0.x for src/include/dijkstra.h
 Timestamp:
 04/22/04 16:50:24 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@503
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/include/dijkstra.h
r335 r373 1 1 // * C++ * 2 3 /*4 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >5 *6 *Constructor:7 *8 *Dijkstra(Graph G, LengthMap length)9 *10 *11 *Methods:12 *13 *void run(Node s)14 *15 *T dist(Node v) : After run(s) was run, it returns the distance from s to v.16 * Returns T() if v is not reachable from s.17 *18 *Edge pred(Node v) : After run(s) was run, it returns the last19 * edge of a shortest sv path. It is INVALID for s and for20 * the nodes not reachable from s.21 *22 *bool reached(Node v) : After run(s) was run, it is true iff v is23 * reachable from s24 *25 */26 2 27 3 #ifndef HUGO_DIJKSTRA_H … … 37 13 namespace hugo { 38 14 39 //Alpar: Changed the order of the parameters40 41 15 ///%Dijkstra algorithm class. 42 16 … … 50 24 ///It is also possible to change the underlying priority heap. 51 25 /// 52 ///\param Graph The graph type the algorithm runs on. 53 ///\param LengthMap This readonly 54 ///EdgeMap 55 ///determines the 56 ///lengths of the edges. It is read once for each edge, so the map 57 ///may involve in relatively time consuming process to compute the edge 58 ///length if it is necessary. The default map type is 59 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 60 ///\param Heap The heap type used by the %Dijkstra 61 ///algorithm. The default 62 ///is using \ref BinHeap "binary heap". 26 ///\param Graph The graph type the algorithm runs on. 27 ///\param LengthMap This readonly EdgeMap determines the lengths of 28 ///the edges. It is read once for each edge, so the map may involve 29 ///in relatively time consuming process to compute the edge length 30 ///if it is necessary. The default map type is \ref 31 ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 32 ///\param Heap The heap type used by the %Dijkstra algorithm. The 33 ///default is using \ref BinHeap "binary heap". 63 34 64 35 #ifdef DOXYGEN … … 104 75 ///of this funcion is undefined. 105 76 ValueType dist(Node v) const { return distance[v]; } 77 106 78 ///Returns the edges of the shortest path tree. 107 79 … … 111 83 ///\pre \ref run() must be called before using this function. 112 84 Edge pred(Node v) const { return predecessor[v]; } 85 113 86 ///Returns the nodes of the shortest paths. 114 87 … … 124 97 /// 125 98 const DistMap &distMap() const { return distance;} 99 126 100 ///Returns a reference to the shortest path tree map. 127 101 … … 130 104 ///\pre \ref run() must be called before using this function. 131 105 const PredMap &predMap() const { return predecessor;} 106 132 107 ///Returns a reference to the map of nodes of shortest paths. 133 108 … … 143 118 ///\todo Is this what we want? 144 119 ///\pre \ref run() must be called before using this function. 145 ///146 120 bool reached(Node v) { return G.valid(predecessor[v]); } 147 121 … … 153 127 // ********************************************************************** 154 128 155 ///Runs %Dijkstra algorithm from node the source.129 ///Runs %Dijkstra algorithm from source node \c s. 156 130 157 131 ///This method runs the %Dijkstra algorithm from a source node \c s 158 ///in order to 159 ///compute the 160 ///shortest path to each node. The algorithm computes 161 /// The shortest path tree. 162 /// The distance of each node from the source. 132 ///in order to compute the shortest path to each node. The algorithm 133 ///computes  The shortest path tree.  The distance of each node 134 ///from the source. 163 135 template <typename Graph, typename LengthMap, 164 136 template<class,class,class> class Heap > … … 169 141 predecessor.set(u,INVALID); 170 142 pred_node.set(u,INVALID); 171 // If a node is unreacheable, then why should be the dist=0?172 // distance.set(u,0);173 // reach.set(u,false);174 143 } 175 144 … … 177 146 178 147 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); 179 180 148 heap.push(s,0); 181 149 182 while ( !heap.empty() ) { 150 while ( !heap.empty() ) { 151 152 Node v=heap.top(); 153 ValueType oldvalue=heap[v]; 154 heap.pop(); 155 distance.set(v, oldvalue); 183 156 184 Node v=heap.top(); 185 ValueType oldvalue=heap[v]; 186 heap.pop(); 187 distance.set(v, oldvalue); 188 189 { //FIXME this bracket is for e to be local 190 OutEdgeIt e; 191 for(G.first(e, v); 192 G.valid(e); G.next(e)) { 157 { //FIXME this bracket is for e to be local 158 OutEdgeIt e; 159 for(G.first(e, v); G.valid(e); G.next(e)) { 193 160 Node w=G.head(e); 194 161 … … 210 177 } 211 178 } 212 } //FIXME t is bracket213 179 } //FIXME this bracket 180 } 214 181 } 215 182
Note: See TracChangeset
for help on using the changeset viewer.