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

[robert dockins]

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:

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.MArray.html

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.



RCP-Software wrote:
> Hi!
> 
> I am new to functional Programming and need some advice. I want to 
> implement Dijkstra's algorithm for the shortest path problem. The 
> algorithm calculates the shortest path from a single vertex in a 
> directed graph to any other connected vertex ( 
> http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ).
> 
> For input and output I need an appropriate graph representation. It 
> should be as simple to implement as possible - speed and memory 
> consumption does not matter. The graph consists of vertices (including 
> the source vertex) and weighted edges. I first thought of an adjacency 
> matrix implemented with nested lists. Something like
>     [[0,1,6,2] , [1,0,2,infinity] , [6,2,0,3] , [2,infinity,3,0]]
> where every sublist represents a vertex, and every entry represents the 
> edge weight to another vertex (infinity means there is no direct 
> connection, and 0 means it points to itself).
> My main problem is that this adjacency list is not so easy to process. 
> For my output I need a tree like structure and I always need to keep 
> track of the previous vertex and its distance etc. Other approaches e.g. 
> structure-like tuples didn't really work - my C experience is worthless.
> 
> Bottom line - I don't what to do. Any help is appreciated.
> 
> TIA, Robert Potthast
> 
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell