// -*- C++ -*- //ha predecessor az elejen nem invalid, akkor hagyd csak ugy //scanned mutatja hogy jo ertek van-e benne vagy szemet /* *template * *Constructor: * *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap length) * * *Member functions: * *void run() * * The following function should be used after run() was already run. * *T dist(NodeIt v) : returns the distance from s to v. * It is 0 if v is not reachable from s. * *EdgeIt pred(NodeIt v) : returns the last edge * of a shortest s-v path. Returns an invalid iterator * if v=s or v is not reachable from s. * *bool reach(NodeIt v) : true iff v is reachable from s * */ #ifndef DIJKSTRA_H #define DIJKSTRA_H #include namespace hugo { template > > class Dijkstra{ typedef typename Graph::NodeIt NodeIt; typedef typename Graph::EdgeIt EdgeIt; typedef typename Graph::OutEdgeIt OutEdgeIt; Graph& G; NodeIt s; typename Graph::NodeMap predecessor; typename Graph::NodeMap distance; typename Graph::EdgeMap& length; typename Graph::NodeMap reached; public : /* The distance of the nodes is 0. */ Dijkstra(Graph& _G, NodeIt const _s, typename Graph::EdgeMap& _length) : G(_G), s(_s), predecessor(G), distance(G), length(_length), reached(G, false) { } void run() { typename Graph::NodeMap scanned(G, false); typename Graph::NodeMap heap_map(G,-1); Heap heap(heap_map); heap.push(s,0); reached.set(s, true); while ( !heap.empty() ) { NodeIt v=heap.top(); T oldvalue=heap.get(v); heap.pop(); distance.set(v, oldvalue); scanned.set(v,true); OutEdgeIt e; for( G.getFirst(e,v); G.valid(e); G.next(e)) { NodeIt w=G.bNode(e); if ( !scanned.get(w) ) { if ( !reached.get(w) ) { reached.set(w,true); heap.push(w,oldvalue+length.get(e)); predecessor.set(w,e); } else if ( oldvalue+length.get(e) < heap.get(w) ) { predecessor.set(w,e); heap.decrease(w, oldvalue+length.get(e)); } } } } } T dist(NodeIt v) { return distance.get(v); } EdgeIt pred(NodeIt v) { if ( v!=s ) return predecessor.get(v); else return EdgeIt(); } bool reach(NodeIt v) { return reached.get(v); } }; } #endif