On Friday, July 1, 2011 11:33:11 AM UTC+1, Andrew wrote: > > - or your priority queue does not provide such an operation, and you > > simply add another entry for y in the priority queue, with a different > > key. It means you have now several entries for y in the priority queue. > > The better will be extracted first; the others will be ignored when they > > are extracted later. Complexity is now O(E log(V)). > > Just an extra question though: How come it's not O(E log (E))? > You could end up pushing as much as one new element in > your heap per edge, couldn't you?
If you use a Set of (distance, vertex) pairs together with min_elt then you can simulate decrease-key using remove followed by add. -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
