2011/4/14 Shaun Jackman <sjackman@bcgsc.ca>

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 <sjackman@bcgsc.ca> 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
> >