On Fri, 1 Jul 2011, Radu Grigore wrote:
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.
You could also keep a map of vertices to distances, so you can update the
distance of a vertex that is not the minimum element without knowing what
it's previous distance was. Something like:
module PQ(Key: Map.Ordered)(Data: Map.Ordered) = struct
module X = struct
type t = Key.t * Data.t;;
let compare (k1, d1) (k2, d2) =
let c = Key.compare k1 k2 in
if (c != 0) then
c
else
Data.compare d1 d2
end
module Y = Set.make(X)
module Z = Map.make(Data)
type t = Y.t * (Key.t Z.t)
let empty : t = Y.empty, Z.empty
let add (s, m) k d =
try
let k' = Z.find d m in
let s = Y.remove (k', d) s in
let s = Y.add (k, d) s in
let m = Z.add d k m in
(s, m)
with
| Not_found ->
let s = Y.add (k, s) s in
let m = Z.add d k m in
(s, m)
let head (s, _) -> snd (Y.min_elt s)
end;;
All the other operations should be obvious.
Brian
--
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
--
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
