Re: [Caml-list] Priority queues

["Jean-Christophe Filliâtre" <Jean-Christophe.Filliatre@lri.fr>]

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

In practice, solution 2 in fast enough. This is what is implemented in
Ocamlgraph(using heaps I mentioned earlier).

See chapter 25 in the Cormen, for instance.

-- 
Jean-Christophe