# 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 Heber Springs 39 Marshall 64.3 Mountain Home 117.1 Mountain View 72.2 Pindall 84.8 Russellville 44.2 Yellville 98.4