
Boost Users : 
Subject: Re: [Boostusers] [BGL] Longest path from u to v in a directed weighted graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20110414 16:15:32
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, 20110413 at 17:21 0700, Murilo Adriano Vasconcelos wrote:
>> The graph is a DAG? If not, that is a NPComplete 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
>
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net