Re: [boost] Dijkstra proof

From: Raja R Harinath (harinath_at_[hidden])
Date: 2002-01-28 23:21:22

Hi,

"David Abrahams" <david.abrahams_at_[hidden]> writes:

> I'm afraid I believe Jeremy's assertion about my algorithm that it's
> O((|V| + |E|) log |E|):  http://groups.yahoo.com/group/boost/message/22906
>
> ...but it looks like you're saying that in any big-O of an algorithm on
> graphs, log |V| can be replaced with log |E|. I see that. Tricky ;-)

Thanks to the power of log :-)

> Now I begin to wonder again when the constant factor makes it a win
> to have an indexable queue, and when it's better to opt for
> simplicity... but, I have no time right now for tests.

While the algorithm is simpler, the worst case memory usage is O(E)
rather than O(V) if you have an indexable queue.  You usually don't
want to square (not double, not triple) your memory usage.

- Hari
-- 
Raja R Harinath ------------------------------ harinath_at_[hidden]
"When all else fails, read the instructions."      -- Cahn's Axiom
"Our policy is, when in doubt, do the right thing."   -- Roy L Ash