# 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`] = `1``e100`

**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

type
and adds the following functions (and constant) that you will
find useful.`Graph`

`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

,
though counting down rather than up),
and a list of name-distance pairs
(corresponding roughly to the Python implementation's `i`

,
though as a list of pairs rather than a dictionary).`results`

If your solution works correctly,

should compute the following distances.`shortestDistances ark` `"Conway"`

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