Boost logo

Boost :

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?


----- 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|):
> >
> > ...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: Send unsubscribe requests to:
> Your use of Yahoo! Groups is subject to

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