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

From: matthieu.ferrant_at_[hidden]
Date: 2005-12-20 10:21:08

Hi Dmitry, Gregoire, zvrba, Aaron, Vladimir,

thanks for your answers to my question.

Gregoire, Vladimir, I initially tried using an all-pairs shortest path algorithm but with a graph of 30.000 nodes or more, the distance matrix is just way to large. That's why I was doing multiple Dijkstras.

Reading the other remarks, I actually ended up doing 2 dijkstras: the first one from an arbitrary end-point, then looping over the distance vector, selecting the end point with the largest distance value associated to it. This is point is then used for a second dijkstra, where I also loop over all end points to determine the other end-point. Finally using the predecessor visitor, and both end points, it is easy to record the full path. This I believe this somewhat boils down to what Aaron wrote. Dmitry, I didn't try out your implementation, looks like it might be a little faster, but what's the overhead of dijkstra vs BFS ? Probably not that much in a tree.

Thanks alot for all the help so far !!

matt-