Re: [Boost-users] stopping dijkstra_shortest_path after target achieved

Yes, it seems to be right. Is the Daniel´s idea, when the desired vertex is permanently labeled (marked black) (you check it with the examine_vertex visitor ), you throw an exception. Sens a little crude to me, but is quite straight forward to implement. i don't know the performance overhead it will cause to call the visitor for every labeled vertex... On 3/14/06, Marcio Paim wrote:

Hello,

I had the same problem, after gathering some information over the net I got this modified version of dijkstra-example.cpp

#include #include <iostream>

#include #include #include

using namespace boost;

// define visitor for discover_vertex event

template struct target_visitor : public default_dijkstra_visitor { target_visitor(Vertex u) : v(u) { }

template <class Graph> void examine_vertex(Vertex u, Graph& g) { if( u == v ) { throw(-1); } } private: Vertex v; };

template target_visitor target_visit(Vertex u, Tag) { return target_visitor(u); }

int main(int argc, char** argv) { typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; typedef std::pair Edge;

const int num_nodes = 5; enum nodes { A, B, C, D, E }; char name[] = "ABCDE"; Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) }; int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 }; int num_arcs = sizeof(edge_array) / sizeof(Edge);

graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); property_map::type weightmap = get(edge_weight, g);

std::vector p(num_vertices(g)); std::vector<int> d(num_vertices(g));

// choose source and target vertex_descriptor src = vertex(A, g); vertex_descriptor targ = vertex(C, g);

try { dijkstra_shortest_paths(g, src,

predecessor_map(&p[0]).distance_map(&d[0]).visitor(target_visit(targ, on_examine_vertex()))); } catch( ... ) { }

std::cout << "distances and parents:" << std::endl; graph_traits < graph_t >::vertex_iterator vi, vend; for (tie(vi, vend) = vertices(g); vi != vend; ++vi) { std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", "; std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::endl; }

system("PAUSE"); return EXIT_SUCCESS; } I compiled it with Dev-C++. I do not understand it in fully detail but I hopefully expect it to be right. Is it right?

m.p.a.

...

...

Is there an easy/already implemented way to stop the computation of the dijkstra_shortest_path algorithm when some target vertex is marked as black??

The recommended method is to use a visitor that throws an exception when

On 3/14/06, Daniel Mitchell wrote: the

...

target is colored black.

Daniel _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users