shortest paths, prioritiy queues
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.
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.
Couldn't Data.Sequence be augmented with the PSQ operations?
On Wed, Dec 24, 2008 at 1:40 PM, 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Wed, Dec 24, 2008 at 02:27:26PM +0100, Lennart Augustsson wrote:
Couldn't Data.Sequence be augmented with the PSQ operations?
Data.Fingertree could be specialized as a PSQ, but I don't see how Data.Sequence could. Insertion would be O((log n)^2), and would also change the position of items in the sequence.
Fair enough.
On Wed, Dec 24, 2008 at 2:58 PM, Ross Paterson
On Wed, Dec 24, 2008 at 02:27:26PM +0100, Lennart Augustsson wrote:
Couldn't Data.Sequence be augmented with the PSQ operations?
Data.Fingertree could be specialized as a PSQ, but I don't see how Data.Sequence could. Insertion would be O((log n)^2), and would also change the position of items in the sequence. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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-... 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.
participants (4)
-
Johannes Waldmann -
Lennart Augustsson -
Martijn van Steenbergen -
Ross Paterson