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