On 12/16/05, matthieu.ferrant@agfa.com <matthieu.ferrant@agfa.com> wrote:

Hi,

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 ?

There's no special algorithm in the BGL for this problem. Finding the longest path in a general graph is a difficult problem, but it happens to be easy for the special case of acyclic graphs. Since acyclic graphs have at most one path between any two vertices, you can use essentially any traversal that measures distances between vertices to find the longest path - as Volodya mentioned, the two all-pairs shortest path algorithms in the BGL can be used. You can also compute the longest path in an acyclic graph in linear time if you want to write a little code yourself. First, assume that the graph is connected - otherwise you could run the algorithm I'm about to describe on all of the connected components and take the maximum-length path you find in any component. If you imagine your tree rooted at some particular vertex v, then there are two cases: either the longest path passes through v, in which case the path starts at one of v's descendants d1, goes up to v through the unique path from d1 to v, then down to another one of v's descendants d2 on the unique path from v to d2. (All of this reasoning follows from the fact that in a tree, there is at most one path between any two vertices.) Otherwise, the longest path doesn't pass through v, and you can effectively remove v from the graph and recursively consider the trees rooted at all of v's children in the same way you just considered v. The easiest way of implementing this is probably a three step process: (1) compute the height of each node in the directed tree rooted by v (2) use the heights from (1) to compute the length of the longest path passing through each vertex, as described above. (3) use the longest path lengths from (2) to assemble the actual longest path. -Aaron