[Haskell-cafe] shortest paths, prioritiy queues

[Ross Paterson]

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.