[Haskell-cafe] shortest paths, prioritiy queues

[Lennart Augustsson]

Couldn't Data.Sequence be augmented with the PSQ operations?

On Wed, Dec 24, 2008 at 1:40 PM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> On Wed, Dec 24, 2008 at 12:23:47PM +0000, Johannes Waldmann wrote:
>> Hello. I am looking for a single-source shortest-path implementation
>> (Dijkstra's algorithm, cf. Chapter 25 in Cormen,Leiserson,Rivest).
>> An efficient implementation would use Binomial or Fibonacci heaps
>> (Chap.s 20 + 21). The problem seems to be "(fib-)heap-decrease-key"
>> which assumes that we have, with the key, a pointer to its position
>> in the heap, because that is where there will be a destructive update.
>> How is this dealt with in Okasaki's book + library? - Thanks, J.W.
>
> The structure you're describing is a priority search queue.  They're not
> covered in Okasaki's book, but Ralf Hinze gave an implementation in ICFP
> 2001, which Scott Dillard has placed on hackage as PSQueue.  They can
> also be implemented using finger trees.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>