Re: [boost] status of fibonnaci_heap and mutable_queue

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

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.

        Doug