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

Subject: Re: [Boost-users] [BGL] Longest path from u to v in a directed weighted graph
From: Shaun Jackman (sjackman_at_[hidden])
Date: 2011-04-14 15:37:10

Hi Murilo,

The subgraph between u and v is a DAG — that is the subgraph reachable
from u without travelling through v. The rest of the graph is not
acyclic.

Cheers,
Shaun

On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote:
> The graph is a DAG? If not, that is a NP-Complete problem and Dijkstra wouldn't help you.
> 
> Regards,
> 
> Murilo Adriano Vasconcelos
> http://murilo.wordpress.com
> 
> Em 13/04/2011, Ã s 21:11, Shaun Jackman <sjackman_at_[hidden]> escreveu:
> 
> > 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