On 2005-02-14, robert dockins <robdockins@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 -><-