// -*- C++ -*- /* *template > * *Constructor: * *Dijkstra(Graph G, LengthMap length) * * *Methods: * *void run(Node s) * *T dist(Node v) : After run(s) was run, it returns the distance from s to v. * Returns T() if v is not reachable from s. * *Edge pred(Node v) : After run(s) was run, it returns the last * edge of a shortest s-v path. It is INVALID for s and for * the nodes not reachable from s. * *bool reached(Node v) : After run(s) was run, it is true iff v is * reachable from s * */ #ifndef HUGO_DIJKSTRA_H #define HUGO_DIJKSTRA_H #include #include namespace hugo { template >, typename LengthMap=typename Graph::EdgeMap > class Dijkstra{ typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt OutEdgeIt; const Graph& G; const LengthMap& length; typename Graph::NodeMap predecessor; typename Graph::NodeMap distance; //FIXME: typename Graph::NodeMap reach; //typename Graph::NodeMap reach; public : /* The distance of the nodes is 0. */ Dijkstra(Graph& _G, LengthMap& _length) : G(_G), length(_length), predecessor(_G), distance(_G), reach(_G) { } void run(Node s) { NodeIt u; for ( G.first(u) ; G.valid(u) ; G.next(u) ) { predecessor.set(u,INVALID); distance.set(u,0); reach.set(u,false); } //FIXME: typename Graph::NodeMap scanned(G,false); //typename Graph::NodeMap scanned(G,false); typename Graph::NodeMap heap_map(G,-1); Heap heap(heap_map); heap.push(s,0); reach.set(s, true); while ( !heap.empty() ) { Node v=heap.top(); T oldvalue=heap.get(v); heap.pop(); distance.set(v, oldvalue); scanned.set(v,true); OutEdgeIt e; for( G.first(e,v); G.valid(e); G.next(e)) { Node w=G.head(e); if ( !scanned[w] ) { if ( !reach[w] ) { reach.set(w,true); heap.push(w,oldvalue+length[e]); predecessor.set(w,e); } else if ( oldvalue+length[e] < heap.get(w) ) { predecessor.set(w,e); heap.decrease(w, oldvalue+length[e]); } } } } } T dist(Node v) { return distance[v]; } Edge pred(Node v) { return predecessor[v]; } bool reached(Node v) { return reach[v]; } }; } #endif