From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UG0M0w017007 for ; Thu, 30 Jun 2011 18:00:22 +0200 X-IronPort-AV: E=Sophos;i="4.65,450,1304287200"; d="scan'208";a="86372388" Received: from lri29-27.lri.fr (HELO [129.175.29.27]) ([129.175.29.27]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 30 Jun 2011 18:00:16 +0200 Message-ID: <4E0C9F14.5000802@lri.fr> Date: Thu, 30 Jun 2011 18:06:44 +0200 From: =?UTF-8?B?SmVhbi1DaHJpc3RvcGhlIEZpbGxpw6J0cmU=?= User-Agent: Thunderbird 2.0.0.24 (X11/20100411) MIME-Version: 1.0 To: David Rajchenbach-Teller CC: caml-list@inria.fr References: <4E0C5E67.9010606@gmail.com> <4E0C6D2E.8070206@lri.fr> <4E0C77EF.6030408@elehack.net> <4E0C8697.8070805@ens-lyon.org> In-Reply-To: <4E0C8697.8070805@ens-lyon.org> X-Enigmail-Version: 0.96.0 OpenPGP: url=http://www.lri.fr/~filliatr/mykey.asc Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] Priority queues > 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