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

On Thu, 14 Apr 2011, Shaun Jackman wrote:

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.

In that case, there is a dag_shortest_paths algorithm that you can use (negating the edge weights). You might need to use filtered_graph (with a prior BFS) to isolate the part of the graph between u and v, or a visitor in the shortest path algorithm might work instead. -- Jeremiah Willcock

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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users