[Haskell-cafe] shortest paths, prioritiy queues

Ross Paterson ross at soi.city.ac.uk
Wed Dec 24 07:40:30 EST 2008

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.

More information about the Haskell-Cafe mailing list