On Tue, 16 Apr 2013, The Maschine wrote:

:) My description of the problem is hopeless. The boost::dijkstra_shortest_paths(m_ugraph, *vertex_iterator_begin, boost::predecessor_map(predecessorMap).distance_map(distanceMap));

currently works ok. Finds the shortest path based on the "edge_weight" (this is what I need).

The addition I need: I need the search for the shortest path to stop if outside a radius. (my graph is a street network).

lets say max "travel distance" = 4  Source -> V1(length=1) -> V2(length=3) -> V3(length=2) -> V4(length=1) -> V5(length=1) ->VEnd

The search should end on V3 and V3 should be "unreachable" from the source (V4,V5 and Vend should be unreachable too)

The distance_map should have the distances for V1 and V2 based on the "edge_weight".

This explanation seems to be better.

What you are probably looking for then is resource-constrained shortest paths; the Boost.Graph algorithm for it is URL:http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/r_c_shortest_paths.h.... See the documentation for that for how to use it; it is more complicated than Dijkstra's algorithm because of the extra restriction, but it also includes an easy way to stop when some resource reachaes its limit (no exception throwing). -- Jeremiah Willcock