From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-04-11 10:25:46
On Apr 11, 2006, at 3:18 AM, David Abrahams wrote:
> Doug Gregor <dgregor_at_[hidden]> writes:
>>> If I understand the propery maps library correctly, I'll need to
>>> create a map, or hash_map, associating each and every possible value
>>> with an int, and wrap that into an associative_property_map<> to
>>> input into the relaxed_heap DS.
>>> Is that right?
>> That sounds right.
> I don't have the context for this discussion (I'm on a plane right now
> and can't see back in time), but I'm going to hazard a wild guess that
> the need to index the nodes is due to the need for a priority queue
> with an update() operation, and that is due to the fact that what
> you're doing is based on dijkstra_shortest_paths.
The mapping from values to integers is needed so that the relaxed
heap can associate extra data with each value.
> A couple years ago Jeremy and I had an argument because I couldn't
> understand the need for this update operation (and its concommitant
> inconveniences), whereas Jeremy, apparently, had never seen a Dijkstra
> that didn't use it. While I understand (or at least I eventually
> understood at the time) how the update could save some computation,
> not doing the update doesn't change the big-O performance of the
Back when you had that argument with Jeremy, the BGL implementation
of Dijkstra's algorithm was using a binary heap, which has O(lg n)
for both update and delete. I've since replaced the binary heap with
the relaxed heap, which provides O(1) update but O(lg n) delete.
> So I'm wondering if the library shouldn't have a version
> of dijkstra that doesn't use the update... or, maybe better yet, if
> update were a free function, maybe the library could provide a default
> one that does nothing.
This would change the complexity of Dijkstra's algorithm from O(|V|
lg |V|) to O(|V| lg |E|), where |V| is the number of vertices in the
graph and |E| is the number of edges in the graph.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk