Re: [Boost-users] Graph problem -- solvable using the Boost graph library ?

From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-12-17 01:53:10

matthieu.ferrant_at_[hidden] wrote:

Hi Matthieu,

as a side remark, please don't use HTML emails,

> I have a non-directed, acyclical graph
> with a series of end points. I need to compute the longest path between
> any two end points.  Right now I do this computing the longest
> dijkstra shortest path (using the boost graph library) from each end point
> and picking the longest of these, but this is quite heavy. Is there a
> faster way to do this ?

http://boost.org/libs/graph/doc/johnson_all_pairs_shortest.html and 
http://boost.org/libs/graph/doc/floyd_warshall_shortest.html allows you to
compute distances between all pairs of vertices and it will be a bit more
efficient than repeative applications of Dijkstra.

- Volodya