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

[Pedro Vasconcelos]

On Mon, 14 Feb 2005 15:00:17 +0100
RCP-Software <rcp-software at web.de> wrote:

> 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).

Robert, if you're not requiring an efficient implementation you can
represent the graph as a list of (weighted) arcs, i.e.

type Node =  Int     -- or whatever you want to label the nodes with
type Weight = Int    -- weights are just ints 
type Arc = (Node, Weight, Node)
type Graph = [Arc]

The type name declarations are just for readability, but also to enforce
that you keep nodes and weights separately (even thought they might both
be integers).

Alternatively, you could also use an adjecency list, but again you
should distinguish nodes and weights:

type Adj = [(Node,Weight)]         -- weighted arcs connecting to nodes 
type AdjGraph = [ (Node, Adj) ]    -- list of adjecencies

In either case, remember that Haskell lists must be homogenous, i.e. you
can't have a weight being either an int or "infinity". You can either
use a special  large value to represent infinity or you'd have to define
a lifted type. I'd recomend you try the first option first.

BTW, these represetations are less efficient than you could write in
e.g. C because you have to traverse a list to find neighbours of a
vertex. It is possible to write more efficient representation using
references or arrays, but I'd stay away from that until you're more
familiar with the language.

Best regards,

Pedro Vasconcelos