Re: [Boost-users] Re: Way to print a route between two nodes

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-08-01 09:30:57

On Jul 30, 2004, at 1:23 AM, Gustavo S˙ffffe1nchez wrote:

> I don't know exactly how you are traversing those nodes in the path, - 
> ie how do find the path -, but as far as I know you have to use a 
> visitor with an algorithm such as dijisktra shortest paths, so you 
> define the event point, on_finish_vertex for example where you want 
> the visitor to be called. This algorithm also stores in a vector the 
> minimum weight pahts encountered from an specific origin vertex so you 
> can go over those paths from the last vertex to this origin.

The best way to get at the shortest paths is to provide a predecessor 
map. The documentation of dijkstra_shortest_paths says:

   "Also you can record the shortest paths tree in a predecessor map: 
for each vertex u in V, p[u] will be the predecessor of u in the 
shortest paths tree (unless p[u] = u, in which case u is either the 
source or a vertex unreachable from the source). In addition to these 
two options, the user can provide there own custom-made visitor that 
can takes actions during any of the algorithm's event points."

        Doug