17 Dec
2005
17 Dec
'05
6:33 p.m.
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