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

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fgl

Or, more specifically:

http://hackage.haskell.org/packages/archive/fgl/5.4.2.2/doc/html/Data-Graph-Inductive-Query-SP.html

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.

Groetjes,

Martijn.


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.

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to