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 date.
(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. Doug