From: David Abrahams (dave_at_[hidden])
Date: 2006-04-13 12:16:00
Douglas Gregor <doug.gregor_at_[hidden]> writes:
> 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.
More importantly to me, it makes usage requirements much more
complicated in some cases.
> 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.
Well, that's great to know.
So, I'll ask my original question again: given that it's a toss-up,
and it is often inconvenient for users, does it make sense to require
a relaxed heap?
-- Dave Abrahams Boost Consulting www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk