[Haskell-cafe] shortest paths, prioritiy queues

Martijn van Steenbergen martijn at van.steenbergen.nl
Wed Dec 24 08:38:05 EST 2008

There is an implementation of Dijkstra's algorithm in the fgl package on 


Or, more specifically:


Although I've never used it yet, so I don't know if it's correct and 
efficient and if the algorithm is anything like the one by Cormen et al.



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.

More information about the Haskell-Cafe mailing list