Doug Gregor <dgregor@cs.indiana.edu> writes:
On Apr 13, 2006, at 12:16 PM, David Abrahams wrote:
Douglas Gregor <doug.gregor@gmail.com> writes: So, I'll ask my original question again: given that it's a toss-up, and it is often inconvenient for users, does it make sense to require a relaxed heap?
Well, the relaxed heap is completely internal to Dijkstra's algorithm. If it were a parameter, the constraint would be for an "Updateable Buffer", e.g., a Buffer (as with BFS) that also has the update() operation.
Okay, I'm obviously misremembering what happened, but IIRC I ended up using my own hand-rolled Dijkstra in libs/python/src/object/inheritance.cpp because the BGL's was imposing several incovenient requirements on me, like tri-state coloring and an update operation for the relaxed heap.
The update() operation is really simple for a binary heap, and important to get the best complexity for Dijkstra algorithm, so we can't remove that requirement.
Doesn't whether it's best depend on the relationship between V and E? -- Dave Abrahams Boost Consulting www.boost-consulting.com