From: David Abrahams (dave_at_[hidden])
Date: 2006-04-15 00:05:06
Doug Gregor <dgregor_at_[hidden]> writes:
> On Apr 13, 2006, at 12:16 PM, David Abrahams wrote:
>> Douglas Gregor <doug.gregor_at_[hidden]> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk