Re: [Caml-list] Priority queues

[Andrew <newsgroups.fr@gmail.com>]

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?