From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p61Aq1R4029519 for ; Fri, 1 Jul 2011 12:52:01 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsAEAKKlDU5bt1HI/2dsb2JhbABSg31FpBSIe69MkHGBK4N7gQwEkjKEdos7 X-IronPort-AV: E=Sophos;i="4.65,457,1304287200"; d="scan'208";a="112324827" Received: from mail.decis.be (HELO decis.be) ([91.183.81.200]) by mail1-smtp-roc.national.inria.fr with ESMTP; 01 Jul 2011 12:51:56 +0200 X-MDAV-Processed: decis.be, Fri, 01 Jul 2011 12:51:55 +0200 Received: from [127.0.0.1] by decis.be (MDaemon PRO v12.0.3) with ESMTP id 44-md50000003651.msg for ; Fri, 01 Jul 2011 12:51:54 +0200 X-Spam-Processed: decis.be, Fri, 01 Jul 2011 12:51:54 +0200 (not processed: message from trusted or authenticated source) X-Authenticated-Sender: fplancke@decis.be X-MDRemoteIP: 192.168.0.30 X-Return-Path: fvdp@decis.be X-Envelope-From: fvdp@decis.be X-MDaemon-Deliver-To: caml-list@inria.fr Message-ID: <4E0DA6C9.2020208@decis.be> Date: Fri, 01 Jul 2011 10:51:53 +0000 From: =?UTF-8?B?RnLDqWTDqXJpYyB2YW4gZGVyIFBsYW5ja2U=?= User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.2.18) Gecko/20110616 Thunderbird/3.1.11 MIME-Version: 1.0 To: "caml-list@inria.fr >> caml-list" References: <4E0C5E67.9010606@gmail.com> <4E0C6D2E.8070206@lri.fr> <4E0C77EF.6030408@elehack.net> <4E0C8697.8070805@ens-lyon.org> <4E0C9F14.5000802@lri.fr> <4E0DA252.1060105@gmail.com> In-Reply-To: <4E0DA252.1060105@gmail.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Antivirus: avast! (VPS 110701-1, 01/07/2011), Outbound message X-Antivirus-Status: Clean Reply-To: fvdp@decis.be Subject: Re: [Caml-list] Priority queues 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