Boost logo

Boost :

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-12 13:48:39

On Nov 12, 2004, at 2:27 AM, Vladimir Prus wrote:

> Doug Gregor wrote:
>> On Nov 6, 2004, at 8:57 AM, Vladimir Prus wrote:
>>> after trying to use the bellman_ford_shortest_paths I think it's a
>>> little bit
>>> strange. First of all, user is required to initialise distance map
>>> before
>>> calling the algorithm. The distance to the source vertex must be set
>>> to zero
>>> and distances to other vertices to infinity. Why can't the algorithm
>>> accept a
>>> source vertex as parameter and do initialisation itself? Dijsktra
>>> surely does
>>> not require such initialization.
>> I believe the intent was to make the Bellman-Ford algorithm require
>> only an Edge List Graph and not also a Vertex List Graph. To set the
>> distance map, one would need the vertices(g) function.
> Do you have a practical case where this matters. How can user
> initialise
> distance map himself without iterating over vertices

You can store information within the vertices and have only the names
of a few of the vertices to start from. For the properties, you keep a
global counter: each time you run the algorithm, you increment the
counter, thereby telling all vertices that their values are out of

> (I'd don't think using
> std::map for distance map is viable for performance reasons).

What about a hash table? That's efficient enough to be viable.
> I would actually drop the existing overload, and provide the one above
> and
> template <class VertexAndEdgeListGraph, class P, class T, class R>
> bool bellman_ford_shortest_paths(
> VertexAndEdgeListGraph& g,
> typename
> graph_traits<VertexAndEdgeListGraph>::vertex_descriptor source,
> unsigned N,......
> for special cases. This might break some code, but interface is really
> better.

Then we are essentially lowering the algorithm by placing on more
requirements. It is a common use case to have a VertexAndEdgeListGraph,
but it isn't the only use case.


Boost list run by bdawes at, gregod at, cpdaniel at, john at