On 1/07/2011 10:32, Andrew wrote:
Jean-Christophe Filliâtre wrote:
Are we talking about Dijkstra's graph traversal algorithm?
If so, there is no need to increase/decrease anything.
Implementing Dijkstra's shortest path algorithm actually requires to
decrease the priority of some nodes. But this does not mean your
priority queue data structure has to support such an operation.
When you consider the edge x->y, x being the node you just extracted
from the priority queue, you might just have discovered a better path to
y and thus you have to update the priority associated to x. When there
is indeed such an improvement, you have two options:
- either your priority queue data structure provides a decrease_key
operation, and then you use it; this is the case with Fibonacci heaps,
an imperative data structures which provides decrease_key in O(1) and
thus makes Dijkstra's algorithm complexity O(V log(V) + E).
- 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?
log(E) is O(log(V)), since log(E) <= 2 * log(V)...
Frédéric
--
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
