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

ajb at spamcop.net ajb at spamcop.net
Mon Feb 14 18:42:08 EST 2005


G'day all.

Quoting robert dockins <robdockins at fastmail.fm>:

> This algorithm relies pretty fundamentally on mutability, which makes it
>   a less than wonderful fit for a functional language.

Right, which makes me wonder if this is the algorithm that you really want.

Does it have to be Dijkstra's algorithm?  Dynamic programming algorithms
(e.g. the Floyd-Warshall algorithm) are very easy to write in a lazy
language like Haskell, because you don't need mutability; you write
"thunks" into a dictionary data structure (which may depend on other
values in the data structure), and let the evaluation rule do the rest.

Cheers,
Andrew Bromage


More information about the Haskell mailing list