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.
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