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

On Thu, 2011-04-14 at 13:15 -0700, Jeremiah Willcock wrote:

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.

Hi Jeremiah, dag_shortest_paths looks promising. It starts by computing a topological ordering of the graph, and in fact I already have a topological ordering of the subgraph in which I'm interested. So, it looks as though I'll just use the algorithm that computes the longest path from the topological ordering. It would be nice if this algorithm were factored so that a user could provide a topological ordering as a parameter. Thanks, 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