Re: [Caml-list] Priority queues

["Frédéric van der Plancke" <fvdp@decis.be>]

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