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.
----- Original Message -----
From: "Raja R Harinath" <harinath_at_[hidden]>
Hence, the expression above simplifies to O(E log V).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk