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

Josef Svenningsson josef.svenningsson at gmail.com
Mon Feb 14 12:52:05 EST 2005


On Mon, 14 Feb 2005 12:27:51 -0500, robert dockins
<robdockins at fastmail.fm> wrote:
> [Dijkstra's] 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).

It is quite possible to implement the shortest path algorithm
functionally even though it is not straight forward. See the following
paper by Ralf Hinze:
http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf

/Josef


More information about the Haskell mailing list