From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p61AWtVK028826
	for <caml-list@sympa-roc.inria.fr>; Fri, 1 Jul 2011 12:32:55 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ah4DAJKhDU5KfVK2kGdsb2JhbAA8AQMShEKUK45qCBQBAQEBCQkNBxQEIYh7pAmLZj6CS4RAOYhoAgMGgSWDe4EMBJIyhHaBHIYMPINZ
X-IronPort-AV: E=Sophos;i="4.65,457,1304287200"; 
   d="scan'208";a="102334129"
Received: from mail-wy0-f182.google.com ([74.125.82.182])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Jul 2011 12:32:49 +0200
Received: by wyg24 with SMTP id 24so3851329wyg.27
        for <caml-list@inria.fr>; Fri, 01 Jul 2011 03:32:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=message-id:date:from:user-agent:mime-version:to:cc:subject
         :references:in-reply-to:content-type:content-transfer-encoding;
        bh=HQFONR3HqyZgGQKjXr38BWLR1exUX9NdmiIUxSyCkrw=;
        b=jARs4FkuTCfcpAe0V6geYY5WVT+KFYGPYknAc+ij21IwpoV8Wkfj70W5KK0ifglbOS
         Y1wTv6enufXFgpxJxIgpTiaoqpe6snv31YJz/Lg286n1oOfPWH0vLP+ncBDb7VurdTMm
         HyCZZMveAFz+2Y70jpPg8oKsuW9UyL8T11HIU=
Received: by 10.227.200.198 with SMTP id ex6mr2837408wbb.2.1309516369367;
        Fri, 01 Jul 2011 03:32:49 -0700 (PDT)
Received: from [192.168.1.187] (106.165.7.93.rev.sfr.net [93.7.165.106])
        by mx.google.com with ESMTPS id o19sm2256791wbh.4.2011.07.01.03.32.47
        (version=SSLv3 cipher=OTHER);
        Fri, 01 Jul 2011 03:32:48 -0700 (PDT)
Message-ID: <4E0DA252.1060105@gmail.com>
Date: Fri, 01 Jul 2011 12:32:50 +0200
From: Andrew <newsgroups.fr@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20110624 Thunderbird/5.0
MIME-Version: 1.0
To: caml-list@inria.fr
CC: Jean-Christophe.Filliatre@lri.fr
References: <4E0C5E67.9010606@gmail.com> <4E0C6D2E.8070206@lri.fr> <4E0C77EF.6030408@elehack.net> <BANLkTin0Z9psTfYm8aDqqXFX3q-6jL_Mmw@mail.gmail.com> <4E0C8697.8070805@ens-lyon.org> <4E0C9F14.5000802@lri.fr>
In-Reply-To: <4E0C9F14.5000802@lri.fr>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [Caml-list] Priority queues

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?