From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UETADA013731 for ; Thu, 30 Jun 2011 16:29:10 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvABAHmHDE7RVaC2kGdsb2JhbAAxCxanTQgUAQEBAQkJDQcUBCGIeKJtjmsBjWIFhjGSM4wcPINX X-IronPort-AV: E=Sophos;i="4.65,450,1304287200"; d="scan'208";a="97734809" Received: from mail-gy0-f182.google.com ([209.85.160.182]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 30 Jun 2011 16:29:04 +0200 Received: by gyf3 with SMTP id 3so1401972gyf.27 for ; Thu, 30 Jun 2011 07:29:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=CQwb/AlVhuRAQ8eAI3dWDrAiE/SIZIJeHReRoUk20ck=; b=Rsi7d4Tw0lhsWVuIQRK+Ai8jhnyVS86eGYh84nl7C1N66Pxvmhf+ToUSKXQ3GOcalX 79eCsaaJ3aXvkKWm9Rh1qZmFfslsx08w5GhIMc+AWMPyM8GhnLNHNAZa9h/VjG4+1CqW 7RQXqi8XuX+jnO+602oiF2R52do7cfuoXG/fU= MIME-Version: 1.0 Received: by 10.150.177.6 with SMTP id z6mr1867247ybe.434.1309444143654; Thu, 30 Jun 2011 07:29:03 -0700 (PDT) Received: by 10.151.43.6 with HTTP; Thu, 30 Jun 2011 07:29:03 -0700 (PDT) In-Reply-To: <4E0C8697.8070805@ens-lyon.org> References: <4E0C5E67.9010606@gmail.com> <4E0C6D2E.8070206@lri.fr> <4E0C77EF.6030408@elehack.net> <4E0C8697.8070805@ens-lyon.org> Date: Thu, 30 Jun 2011 15:29:03 +0100 Message-ID: From: Wojciech Meyer To: David Rajchenbach-Teller Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=000e0cd6a87609291304a6eeb93f X-Validation-by: wojciech.meyer@googlemail.com Subject: Re: [Caml-list] Priority queues --000e0cd6a87609291304a6eeb93f Content-Type: text/plain; charset=ISO-8859-1 On Thu, Jun 30, 2011 at 3:22 PM, David Rajchenbach-Teller < David.Teller@ens-lyon.org> wrote: > On 6/30/11 4:07 PM, Alexandre Pilkiewicz wrote: > >> I have the impression that none of the proposed solution allows to >> increase/reduce the priority of an element, which is necessary for the >> Dijkstra. (But I don't know any that does) >> >> - Alexandre >> > Are we talking about Dijkstra's graph traversal algorithm? > If so, there is no need to increase/decrease anything. > Exactly, I think in that way as well. (in case if it's shortest path problem). And if one does not need performance but understanding what's the purpose of the priority queue is, what is the interface, and how it should behave, than implementation as a list is sufficient. Please note it is for exam and major pressure is put on Dijkstra not on implementation or performance (as far as I understood) of the priority queue. (which can be changed later easily) > Best regards, > David > Cheers; Wojciech --000e0cd6a87609291304a6eeb93f Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

On Thu, Jun 30, 2011 at 3:22 PM, David R= ajchenbach-Teller <David.Teller@ens-lyon.org> wrote:
On 6/30/11 4:07 PM, Alexandre Pilkiewicz wrote:
I have the impression that none of the proposed solution allows to
increase/reduce the priority of an element, which is necessary for the
Dijkstra. (But I don't know any that does)

- Alexandre
Are we talking about Dijkstra's graph traversal algorithm?
If so, there is no need to increase/decrease anything.

Exactly, I think in that way as well. (in case if it's shortest pa= th problem).

And if one does not need performance but understanding= what's the purpose of the priority queue is,
what is the interface, and how it should behave, than implementation as a l= ist is sufficient. Please note
it is for exam and major pressure is put = on Dijkstra not on implementation or performance (as far as I
understoo= d) of the priority queue. (which can be changed later easily)


Best regards,
=A0David

Cheers;Wojciech


--000e0cd6a87609291304a6eeb93f--