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: http://lists.boost.org/mailman/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk