[Haskell] Re: [Newbie] Data structure for Dijkstra's algorithm
wnoise at ofb.net
Mon Feb 14 14:19:03 EST 2005
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.
> 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.
I still think there should be some clever way to do this using lazy
evaluation, but it's not at all clear how.
More information about the Haskell