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(gsrc):
    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(uv))

    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 -> [(StringDouble)]
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.

Clinton38.2
Conway0.0
Heber Springs39.0
Marshall64.3
Mountain Home117.1
Mountain View72.2
Pindall84.8
Russellville44.2
Yellville98.4