Assignment 3: Shortest paths in Haskell
Due: 5:00pm, Friday, September 14. Value: 30 pts.
In this assignment, we'll translate a fairly complex algorithm written in an imperative paradigm into the purely functional paradigm represented by Haskell. In particular, your assignment is to implement the Bellman-Ford algorithm for finding all distances from a starting node in a graph. For your reference, below is an implementation of the algorithm using Python.
def bellman_ford(g, src):
result = {}
for v in g.nodes:
if v == src:
result[v] = 0
else:
result[v] = 1e100
for i in range(len(g.nodes) - 1):
for v in g.nodes:
for u in g.neighbors(v):
result[v] = min(result[v], result[u] + g.weight(u, v))
return result
Representing the graph is first task, which I have completed
in the file graph.hs.
[Download.] This file creates a Graph type
and adds the following functions (and constant) that you will
find useful.
nodes :: Graph -> [String]- Given a graph, return a list of all nodes' names.
neighbors :: Graph -> String -> [String]- Given a graph and one node's name, return a list of names for all nodes connected to that node.
weight :: Graph -> String -> String -> Double- Given a graph and two nodes' names, return the length of the edge connecting those two nodes.
ark :: Graph- A sample graph for testing purposes, including the distances between a variety of towns in the Arkansas Ozarks (map is above at right).
Your assignment is to modify this file where indicated to add the following function.
shortestDistances :: Graph -> String -> [(String, Double)]- Given a graph and the name of some node s, return a list containing a tuple for every node t in the graph; each tuple should contain t's name followed by the length of the shortest path from s to t. The distances are computed using the Bellman-Ford algorithm.
To translate the Bellman-Ford algorithm into Haskell, I suggest
creating a helper function that takes three parameters:
the graph, the number of iterations remaining
(corresponding roughly to the Python implementation's i,
though counting down rather than up),
and a list of name-distance pairs
(corresponding roughly to the Python implementation's results,
though as a list of pairs rather than a dictionary).
If your solution works correctly, shortestDistances ark "Conway"
should compute the following distances.
Clinton 38.2 Conway 0.0 Heber Springs 39.0 Marshall 64.3 Mountain Home 117.1 Mountain View 72.2 Pindall 84.8 Russellville 44.2 Yellville 98.4