Re: [Boost-users] [graph] dijkstra additional constrains that will stop the search (ex. distance from source)

Subject: Re: [Boost-users] [graph] dijkstra additional constrains that will stop the search (ex. distance from source)
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-04-16 16:29:02

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.html>. 
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