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: Murilo Adriano Vasconcelos (muriloufg_at_[hidden])
Date: 2011-04-13 20:21:13

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
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users