Re: [Boost-users] Longest path from u to v in a directed weighted graph

Subject: Re: [Boost-users] Longest path from u to v in a directed weighted graph
From: Richard Damon (Richard_at_[hidden])
Date: 2011-04-14 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