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

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2005-12-17 13:33:58

>>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 ?
>>    
>>
Hi,
Unfortunately I didn't test, but I'm pretty sure, that for acyclic  
graphs Dijkstra's algorithm has linear complexity (you don't need color 
map at all), and you don't need to find all connected components, so 
your current approach is the best solution or very close to the best=)
--dima