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

From: Grégoire Dooms (dooms_at_[hidden])
Date: 2005-12-19 02:18:39

matthieu.ferrant_at_[hidden] 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.
>
Do you need the longest path or the longest among the all pairs shortest 
paths ?

>  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 ?
>
>  
>
You can use all pairs shortest path algorithms (see other answer in this 
thread).

If you really want the longest path, just transform the costs: use  the 
opposite cost ( - c ) for each edge. Then search the shortest one and 
you will get the longest path in your original graph. Such a path is 
garanteed to exist as your graph is acyclical so there are no negative 
cycles in your graph.

If you have a relatively small number of end points, just add an 
additional source to all the end points and an additional sink from all 
endpoints. Then use point to point shortest path such as Bellman-Ford 
from the added source to the added source.  You need to find appropriate 
equal costs for all the added edges. If your longest path has positive 
cost, using 0 for the cost of the new edges should be correct: an all 
virtual path has cost 0 while the shortest one is negative ie. lower.

HTH,
--
Grégoire Dooms