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

Hi, 2011/4/14 Shaun Jackman

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

...

...

...

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

On Wed, 2011-04-13 at 17:21 -0700, Murilo Adriano Vasconcelos wrote: 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

If you already have a topological ordering of your subgraph, you only need to do one DFS to find the longest path. You can just do a DFS starting from the vertex with in-degree 0 (the root of topological tree) (if your subgraph is not connected, you'll need to do a DFS from each vertex with in-degree 0) and save the maximum depth you find. Regards, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com