Re: [boost] Dijkstra proof

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-29 07:21:12

True, but in my case I know something about the graphs: their connectivity
just isn't all that high. Qualitative domain knowledge must come into play
often in real world graph processing, no?

-Dave

----- Original Message -----
From: "Raja R Harinath" <harinath_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, January 28, 2002 11:21 PM
Subject: Re: [boost] Dijkstra proof

> 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
>
> Info: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>