Fair enough.
On Wed, Dec 24, 2008 at 2:58 PM, Ross Paterson wrote:
> 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. I
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 i
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
Couldn't Data.Sequence be augmented with the PSQ operations?
On Wed, Dec 24, 2008 at 1:40 PM, Ross Paterson wrote:
> On Wed, Dec 24, 2008 at 12:23:47PM +, Johannes Waldmann wrote:
>> Hello. I am looking for a single-source shortest-path implementation
>> (Dijkstra's algorithm, cf. Chapter 25
On Wed, Dec 24, 2008 at 12:23:47PM +, 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
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, w
