
Boost Users : 
Subject: Re: [Boostusers] Longest path from u to v in a directed weighted graph
From: Richard Damon (Richard_at_[hidden])
Date: 20110414 17:37:12
On 4/13/11 8:11 PM, Shaun Jackman wrote:
> Hi,
>
> I would like to find the longest path from vertex u to vertex v through
> a directed graph with positive edge weights. I know that u and v are
> choke points in the graph, in that if you start from vertex u and start
> following random edges, you will end up at vertex v in pretty short
> order. Is dijkstra_shortest_paths the best function for this purpose?
>
> The vertices reachable from u without travelling through v form a small
> subgraph of the total graph. I want to avoid exploring beyond v, and I
> definitely don't need to know the distances to vertices beyond v.
>
> Cheers,
> Shaun
>
Thinking about this a bit, to find the LONGEST length will by necessity
require every path, because there is no way to trim a set of paths and
say they can't be longer then the current longest. Shortest finding
algorithms can trim the search space since once you get from u to a in
distance d, once your current path is bigger than d you don't need to
check going through a anymore.
Since you say it forms a small DAG, a quick depth first search, keeping
track of the longest path may be best.
 Richard Damon
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net