[Haskell] [Newbie] Data structure for Dijkstra's algorithm
RCP-Software
rcp-software at web.de
Mon Feb 14 09:00:17 EST 2005
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
More information about the Haskell
mailing list