[Haskell-cafe] shortest paths, prioritiy queues

Johannes Waldmann waldmann at imn.htwk-leipzig.de
Wed Dec 24 07:23:47 EST 2008

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.

More information about the Haskell-Cafe mailing list