Re: [boost] How to find all paths with a length in a certain range

Subject: Re: [boost] How to find all paths with a length in a certain range
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-07-18 17:38:37

On Tue, 17 Jul 2012, J Birch wrote:

> I am fairly new to Boost, and not the greatest at C++, but I do have a 
> bit of experience in dealing with graphs in other languages.
>
> We currently have some very ugly and inefficient code that effectively 
> builds up a graph structure (DAG), and must calculate all paths with a 
> length between a certain range, say 3-7.
>
> I have seen the question asked a few times via Google, but I have seen 
> no solution.  I have been tinkering around with different examples, but 
> have yet to come up with anything useful.
>
> Would anyone be able to point me in the right direction?

You might want to use dynamic programming on the graph, traversing it in a 
reverse topological order.  See 
http://stackoverflow.com/questions/2207987/cheapest-path-algorithm for 
information on a related problem.

-- Jeremiah Willcock