Boost logo

Boost :

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


> --
> Dave Abrahams
> Boost Consulting
> _______________________________________________
> Unsubscribe & other changes:
> listinfo.cgi/boost

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