Boost logo

Boost :

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-14 10:25:58

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. 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.

Should we use the relaxed heap at all? I'm not sure. I need to check
what's happening on really big graphs to see if the relaxed heap
starts to shine there. I was only working with graphs up to about 1M
vertices previously.


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