# Changeset 78:ecc1171307be in lemon-0.x

Ignore:
Timestamp:
02/16/04 17:15:58 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@101
Message:

modern valtozat

Location:
src/work/jacint
Files:
4 edited

Unmodified
Removed
• ## src/work/jacint/dijkstra.hh

 r50 *dijkstra *by jacint *Performs Dijkstra's algorithm from node s. *Performs Dijkstra's algorithm from Node s. * *Constructor: * *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance) *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance) * * * * *T dist(node_iterator v) : returns the distance from s to v. *T dist(NodeIt v) : returns the distance from s to v. *   It is 0 if v is not reachable from s. * * *edge_iterator pred(node_iterator v) *   Returns the last edge of a shortest s-v path. *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(node_iterator v) : true if v is reachable from s *bool reach(NodeIt v) : true if v is reachable from s * * #include #include #include template class dijkstra{ typedef typename graph_traits::node_iterator node_iterator; typedef typename graph_traits::edge_iterator edge_iterator; typedef typename graph_traits::each_node_iterator each_node_iterator; typedef typename graph_traits::in_edge_iterator in_edge_iterator; typedef typename graph_traits::out_edge_iterator out_edge_iterator; typedef typename graph_traits::NodeIt NodeIt; typedef typename graph_traits::EdgeIt EdgeIt; typedef typename graph_traits::EachNodeIt EachNodeIt; typedef typename graph_traits::InEdgeIt InEdgeIt; typedef typename graph_traits::OutEdgeIt OutEdgeIt; graph_type& G; node_iterator s; node_property_vector predecessor; node_property_vector distance; edge_property_vector length; node_property_vector reached; NodeIt s; NodeMap predecessor; NodeMap distance; EdgeMap length; NodeMap reached; public : /* The distance of all the nodes is 0. The distance of all the Nodes is 0. */ dijkstra(graph_type& _G, node_iterator _s, edge_property_vector& _length) : dijkstra(graph_type& _G, NodeIt _s, EdgeMap& _length) : G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } /*By Misi.*/ struct node_dist_comp struct Node_dist_comp { node_property_vector &d; node_dist_comp(node_property_vector &_d) : d(_d) {} NodeMap &d; Node_dist_comp(NodeMap &_d) : d(_d) {} bool operator()(const node_iterator& u, const node_iterator& v) const bool operator()(const NodeIt& u, const NodeIt& v) const { return d.get(u) < d.get(v); } }; void run() { node_property_vector scanned(G, false); std::priority_queue, node_dist_comp> heap(( node_dist_comp(distance) )); NodeMap scanned(G, false); std::priority_queue, Node_dist_comp> heap(( Node_dist_comp(distance) )); heap.push(s); while (!heap.empty()) { node_iterator v=heap.top(); NodeIt v=heap.top(); heap.pop(); if (!scanned.get(v)) { for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) { node_iterator w=G.head(e); for(OutEdgeIt e=G.template first(v); e.valid(); ++e) { NodeIt w=G.head(e); if (!scanned.get(w)) { /* *Returns the distance of the node v. *It is 0 for the root and for the nodes not *Returns the distance of the Node v. *It is 0 for the root and for the Nodes not *reachable form the root. */ T dist(node_iterator v) { T dist(NodeIt v) { return -distance.get(v); } /* *  Returns the last edge of a shortest s-v path. *  Returns the last Edge of a shortest s-v path. *  Returns an invalid iterator if v=root or v is not *  reachable from the root. */ edge_iterator pred(node_iterator v) { EdgeIt pred(NodeIt v) { if (v!=s) { return predecessor.get(v);} else {return edge_iterator();} else {return EdgeIt();} } bool reach(node_iterator v) { bool reach(NodeIt v) { return reached.get(v); }