Re: [boost] status of fibonnaci_heap and mutable_queue

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-04-12 20:30:49

On Apr 12, 2006, at 5:10 PM, David Abrahams wrote:

> Douglas Gregor <doug.gregor_at_[hidden]> writes:
>
>> 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.
>
> Hmm, did you see:
> http://lists.boost.org/Archives/boost/2002/01/23970.php
> and the foregoing thread?

I've read it now. So I'll be more careful with the complexity measures:

With a relaxed heap it's O(|V| lg |V| + |E|)
With a binary heap it's O((|V| + |E|) lg |V|)

If you insert instead of updating, that, lg |V| becomes a lg |E|.

The relaxed heap is admittedly complicated. We have some performance  
test's we've run, and it's a toss-up. On some graphs, the binary heap  
does slightly better; on others, the relaxed heap does slightly better.

        Doug

> -- 
> Dave Abrahams
> Boost Consulting
> www.boost-consulting.com
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/ 
> listinfo.cgi/boost