[Haskell] Re: [Newbie] Data structure for Dijkstra's algorithm

[Aaron Denney]

On 2005-02-14, robert dockins <robdockins at fastmail.fm> wrote:
> This algorithm relies pretty fundamentally on mutability, which makes
> it a less than wonderful fit for a functional language.

True

> If you want to use this algorithm in particular, I would recommend a
> mutable array indexed on the vertex pair (u,v).  See:

But this is overkill.  An intertwined priority queue and a mutable
mapping from vertices to distances and current shortest path works fine.

> These will require your program to be in the IO or ST monads. 
> Alternately, you could do it fully functionally using Data.FiniteMap, 
> but I don't think you will be happy with the performance.
>
> If you just want to solve the shortest path problem, it may be possible 
> to come up with something using the Data.Graph module, although you 
> might have to dig around in the module source to get at what you need. 
> There's a lot of goodies not exported from that module.

Reasonable advice.

I still think there should be some clever way to do this using lazy
evaluation, but it's not at all clear how.

-- 
Aaron Denney
-><-