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