Re: [boost] Dijkstra proof

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-28 20:52:28

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 ;-)

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.

-Dave

----- Original Message -----
From: "Raja R Harinath" <harinath_at_[hidden]>
...

Hence, the expression above simplifies to O(E log V).