Date: Fri, 07 Apr 2006 11:39:20 +0200 From: Steven Van Ingelgem <steven.vaningelgem@dpd.be> Subject: [Boost-users] Boost Graph Library: Shortest path problem To: boost-users@lists.boost.org Message-ID: <D3D675A5A7892D4287068E36BAFABB91016EC6DD@dcexch2.dpdbe.com> Content-Type: text/plain; charset=us-ascii

Hi,

I have a problem with using (actually with finding the correct function for my problem) the BGL.

What I have is 5000 cities (vertices), 14000 roads (edges) between them (directional roads)... And what I want to know is which roads I have to take to encounter the least cities on my way.

Simple answer: take no road at all ;-)

Every edge has a weight of 1... So the documentation points me to using the breadth_first_search algorithm.

But this function - as far as I can see - goes through the entire graph. I don't see any way to stop it (for example when it has discovered my targetcity)??

Sorry about that, I did know you had a target city. If you want to stop at the target city, the short answer is : use a visitor and throw an exception. void breadth_first_search(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, Buffer& Q, BFSVisitor vis, ColorMap color); The BFSVisitor can be made with the make_bfs_visitor http://www.boost.org/libs/graph/doc/bfs_visitor.html pass it an eventlist made of a predecessor_recorder and a custom eventprocessor use breadth_first_search(g, s, Q, make_bfs_visitor(make_pair(record_predecessors(predecessor_map, on_tree_edge), my_eventvisitor(target_node)), colormap) with struct my_eventvisitor : public boost::base_visitor<my_eventvisitor>{ typedef boost::on_finish_vertex event_filter; Graph::vertex_descriptor target; my_eventvisitor(Graph::vertex_descriptor target): target(target) {} template <class Vertex, class Graph> void operator()(Vertex v, Graph& g) { if (v==target){ throw TargetDiscoveredException; } }; I did not try to compile this but it should be along the lines of what you are looking for.

Is it possible someone can point me where I can have a look at? In short I need to calculate (a lot) of roads from different cities to other cities (so it's not that I always have the same root vertex).

If you have to compute the distance for nearly all pairs of cities, you might want to look for one of the all pairs shortest paths. Hope this helps, -- Gregoire Dooms