00001 #ifndef DIJKSTRA_H 00002 #define DIJKSTRA_H 00003 00004 #include <Structs/Trees/priorityQueue.h> 00005 00006 00019 template<class GraphType> 00020 class Dijkstra 00021 { 00022 public: 00023 typedef typename GraphType::NodeIterator NodeIterator; 00024 typedef typename GraphType::EdgeIterator EdgeIterator; 00025 typedef typename GraphType::SizeType SizeType; 00026 typedef unsigned int WeightType; 00027 typedef PriorityQueue< WeightType, NodeIterator, HeapStorage> PriorityQueueType; 00028 00035 Dijkstra( GraphType& graph, unsigned int* timestamp):G(graph),m_timestamp(timestamp) 00036 { 00037 } 00038 00044 void buildTree( const typename GraphType::NodeIterator& s) 00045 { 00046 NodeIterator u,v,lastNode; 00047 EdgeIterator e,lastEdge; 00048 00049 pq.clear(); 00050 ++(*m_timestamp); 00051 s->dist = 0; 00052 s->timestamp = (*m_timestamp); 00053 s->pred = G.nilNodeDescriptor(); 00054 00055 pq.insert( s->dist, s, &(s->pqitem)); 00056 00057 while( !pq.empty()) 00058 { 00059 u = pq.minItem(); 00060 pq.popMin(); 00061 00062 for( e = G.beginEdges(u), lastEdge = G.endEdges(u); e != lastEdge; ++e) 00063 { 00064 v = G.target(e); 00065 00066 if( v->timestamp < (*m_timestamp)) 00067 { 00068 v->pred = u->getDescriptor(); 00069 v->dist = u->dist + e->weight; 00070 v->timestamp = (*m_timestamp); 00071 pq.insert( v->dist, v, &(v->pqitem)); 00072 } 00073 else if( v->dist > u->dist + e->weight ) 00074 { 00075 v->pred = u->getDescriptor(); 00076 v->dist = u->dist + e->weight; 00077 pq.decrease( v->dist, &(v->pqitem)); 00078 } 00079 } 00080 } 00081 } 00082 00090 WeightType runQuery( const typename GraphType::NodeIterator& s, const typename GraphType::NodeIterator& t) 00091 { 00092 NodeIterator u,v,lastNode; 00093 EdgeIterator e,lastEdge; 00094 00095 pq.clear(); 00096 ++(*m_timestamp); 00097 s->dist = 0; 00098 s->timestamp = (*m_timestamp); 00099 s->pred = G.nilNodeDescriptor();; 00100 00101 pq.insert( s->dist, s, &(s->pqitem)); 00102 00103 while( !pq.empty()) 00104 { 00105 u = pq.minItem(); 00106 pq.popMin(); 00107 if( u == t) break; 00108 for( e = G.beginEdges(u), lastEdge = G.endEdges(u); e != lastEdge; ++e) 00109 { 00110 v = G.target(e); 00111 00112 if( v->timestamp < (*m_timestamp)) 00113 { 00114 v->pred = u->getDescriptor(); 00115 v->dist = u->dist + e->weight; 00116 v->timestamp = (*m_timestamp); 00117 pq.insert( v->dist, v, &(v->pqitem)); 00118 } 00119 else if( v->dist > u->dist + e->weight ) 00120 { 00121 v->pred = u->getDescriptor(); 00122 v->dist = u->dist + e->weight; 00123 pq.decrease( v->dist, &(v->pqitem)); 00124 } 00125 } 00126 } 00127 return t->dist; 00128 } 00129 00130 private: 00131 GraphType& G; 00132 unsigned int* m_timestamp; 00133 PriorityQueueType pq; 00134 }; 00135 00136 00137 00150 template<class GraphType> 00151 class BackwardDijkstra 00152 { 00153 public: 00154 typedef typename GraphType::NodeIterator NodeIterator; 00155 typedef typename GraphType::NodeDescriptor NodeDescriptor; 00156 typedef typename GraphType::EdgeIterator EdgeIterator; 00157 typedef typename GraphType::InEdgeIterator InEdgeIterator; 00158 typedef typename GraphType::SizeType SizeType; 00159 typedef unsigned int WeightType; 00160 typedef PriorityQueue< WeightType, NodeIterator, HeapStorage> PriorityQueueType; 00161 00168 BackwardDijkstra( GraphType& graph, unsigned int* timestamp):G(graph),m_timestamp(timestamp) 00169 { 00170 } 00171 00177 void buildTree( const typename GraphType::NodeIterator& t) 00178 { 00179 NodeIterator u,v,lastNode; 00180 InEdgeIterator k,lastInEdge; 00181 00182 pqBack.clear(); 00183 ++(*m_timestamp); 00184 t->distBack = 0; 00185 t->timestamp = (*m_timestamp); 00186 t->succ = G.nilNodeDescriptor();; 00187 00188 pqBack.insert( t->distBack, t, &(t->pqitemBack)); 00189 00190 while( !pqBack.empty()) 00191 { 00192 u = pqBack.minItem(); 00193 pqBack.popMin(); 00194 for( k = G.beginInEdges(u), lastInEdge = G.endInEdges(u); k != lastInEdge; ++k) 00195 { 00196 v = G.source(k); 00197 00198 if( v->timestamp < (*m_timestamp)) 00199 { 00200 v->succ = u->getDescriptor(); 00201 v->distBack = u->distBack + k->weight; 00202 v->timestamp = (*m_timestamp); 00203 pqBack.insert( v->distBack, v, &(v->pqitemBack)); 00204 } 00205 else if( v->distBack > u->distBack + k->weight ) 00206 { 00207 v->succ = u->getDescriptor(); 00208 v->distBack = u->distBack + k->weight; 00209 pqBack.decrease( v->distBack, &(v->pqitemBack)); 00210 } 00211 } 00212 } 00213 } 00214 00222 WeightType runQuery( const typename GraphType::NodeIterator& s, const typename GraphType::NodeIterator& t) 00223 { 00224 NodeIterator u,v,lastNode; 00225 InEdgeIterator k,lastInEdge; 00226 00227 pqBack.clear(); 00228 ++(*m_timestamp); 00229 t->distBack = 0; 00230 t->timestamp = (*m_timestamp); 00231 t->succ = G.nilNodeDescriptor();; 00232 00233 pqBack.insert( t->distBack, t, &(t->pqitemBack)); 00234 00235 while( !pqBack.empty()) 00236 { 00237 u = pqBack.minItem(); 00238 pqBack.popMin(); 00239 if( u == s) break; 00240 for( k = G.beginInEdges(u), lastInEdge = G.endInEdges(u); k != lastInEdge; ++k) 00241 { 00242 v = G.source(k); 00243 00244 if( v->timestamp < (*m_timestamp)) 00245 { 00246 v->succ = u->getDescriptor(); 00247 v->distBack = u->distBack + k->weight; 00248 v->timestamp = (*m_timestamp); 00249 pqBack.insert( v->distBack, v, &(v->pqitemBack)); 00250 } 00251 else if( v->distBack > u->distBack + k->weight ) 00252 { 00253 v->succ = u->getDescriptor(); 00254 v->distBack = u->distBack + k->weight; 00255 pqBack.decrease( v->distBack, &(v->pqitemBack)); 00256 } 00257 } 00258 } 00259 00260 u = s; 00261 t->dist = 0; 00262 EdgeIterator e; 00263 while( u->succ != G.nilNodeDescriptor()) 00264 { 00265 v = G.getNodeIterator( u->succ); 00266 e = G.getEdgeIterator( u, v); 00267 t->dist += e->weight; 00268 v->pred = G.getNodeDescriptor(u); 00269 u = v; 00270 } 00271 return t->dist; 00272 } 00273 00274 private: 00275 GraphType& G; 00276 unsigned int* m_timestamp; 00277 PriorityQueueType pqBack; 00278 }; 00279 00280 #endif//DIJKSTRA_H 00281