[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