
Boost : 
From: Doug Gregor (dgregor_at_[hidden])
Date: 20041111 13:47:03
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 BellmanFord 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. However, I agree
that it's a bit messy to use, especially when you already have a Vertex
List Graph.
> Another problem is that number of vertices is passed as parameter. I
> realize
> this is more flexible (for example I can compute the maximum length of
> all
> paths with less than N edges), but it's also confusing and dangerous.
> I've
> just passed a wrong variable to that parameter and spend quite some
> time
> debugging.
Same reason: getting n requires num_vertices(g), part of the Vertex
List Graph concept.
> Is it possible to provide a version of the algorithm which
> (1) takes just graph, without vertex number parameter
> (2) takes start vertex, and initialises distance map itself
I expect it would look like this:
template <class VertexAndEdgeListGraph, class P, class T, class R>
bool bellman_ford_shortest_paths(
VertexAndEdgeListGraph& g,
typename
graph_traits<VertexAndEdgeListGraph>::vertex_descriptor source,
const bgl_named_params<P, T, R>& params = all defaults);
I'm slightly concerned that adding this overload will cause an
ambiguity with the existing bellman_ford_shortest_paths when we have an
adjacency list with VertexListS=vecS, but maybe we can weasel around
that...
One alternative would be to have:
template <class VertexAndEdgeListGraph, class P, class T, class R>
bool bellman_ford_shortest_paths(
VertexAndEdgeListGraph& g,
const bgl_named_params<P, T, R>& params = all defaults);
Where the mandatory named parameter start_vertex(u) indicates that we
should initialize the property maps appropriately for starting at
vertex u, and requires a VertexAndEdgeListGraph. This is the safe
answer, at least.
Doug
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk