Exercise 3: Bellman Ford and Graph Potentials

CMPUT 275 Wi18 - INTRO TO TANGIBLE COMPUT II
Combined LBL Wi18
Exercise 3: Bellman Ford and Graph Potentials
The purpose of this exercise is to:
Learn and implement yet another (very simple) algorithm for finding least-cost paths in graphs.
This algorithm can handle negative-cost edges, unlike Dijkstra's (without extra work). It just runs
slower, which is why we cannot use it for the driving route finder.
Understand that we do not always need to build and use a big graph class to process graph data.
Learn how to build the vertex function from Dijkstra's worksheet so we can use Dijkstra's algorithm
in graphs that might have negative-cost edges, as long as there are no negative-cost cycles.
Note: you have two implementation tasks mentioned below. Pay close attention to
the code submission instructions below.
1) The Bellman-Ford Algorithm
Given a graph G = (V;E) and a start vertex s where each edge uv has a cost, say cost(u,v), we often
want to find a least-cost path from s to other reachable vertices. In some cases costs may be negative!
Such an instance may occur when, say, edges represent gains or losses in energy. For example, edges
could represent gains or losses in energy when driving some electric cars: braking while going
downhill may gain energy.
If the graph has cycles whose total edge cost is negative, then this may not be well-defined. We could
just run around such cycles forever to make the path arbitrarily cheap. Of course, in real life this
doesn't really happen: I expect most if not all "natural" graphs we actually want to find paths in will not
have negative cost cycles. In this part, you may assume the graphs to not have negative-cost
cycles.
The Bellman-Ford algorithm finds shortest paths from a vertex s to all other reachable vertices in
O(|V| * |E|) time. It maintains two dictionaries:
dist - Keys are vertices. dist[v] stores a value, perhaps infinity
reached - Same as with all other searches. Maps vertices to predecessors on the search t
ree
At each step of the algorithm, the reached dictionary is a search tree to some reachable vertices. But it
may not represent shortest paths until the end of the algorithm, and may even change its edges over
time to vertices that are already reached.
The pseudocode is very simple:
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
1 of 5 2018-04-14, 1:00 p.m.
dist <-- dictionary mapping s to 0 and every other vertex to infinity
reached <-- dictionary mapping s to s, and nothing else
for |V|-1 iterations do
for each edge (u,v) do
if dist[v] dist[u] + cost(u,v)
dist[v] = dist[u] + cost(u,v)
reached[v] = u
At the end, reached will be a search tree representing minimum-cost paths and dist[v] will be the
cost of this minimum-cost path from s to v (still infinity if v was not reached).
Why does this work? You can prove that after k iterations that dist[v] is at most the cost of the
cheapest path to v using at most k edges. This is why |V|-1 iterations suffice.
Your First Job
Implement the Bellman-Ford algorithm as the following function. Note you should not use the Graph
class we developed. Adhere exactly to the specification.
def bellman_ford(vertices, edges, start):
'''
Computes shortest paths to every reachable vertex from the vertex "start"
in the given directed graph.
vertices: the set of vertices in the graph.
edges: maps pairs of vertices to values representing edge costs
example - {('A', 'B'): -3} means the edge from vertex
'A' to vertex 'B' has cost -3
start: the start vertex to search from

Assumes the graph does not have negative cost cycles,
that all edges have endpoints in "vertices", and that
"start" is also in "vertices".
returns dist, reached
Here reached is the search tree to all reachable vertices along
minimum-cost paths and dist[v] is the cost to v along
this path. If v is not reachable, it should not be in the
search tree nor an index in dist.
'''
Helpful tips:
The floating point type actually supports the value infinity: float('inf'). It works as you expect:
infinity plus any finite number is still infinity (though infinity - infinity is not defined). Use it at
your discretion (i.e. you are not required to use it).
1.
If you define entries in dist for vertices that are not reachable, remember to remove them before
returning from the bellman_ford function.
2.
2) Graph Potentials
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
2 of 5 2018-04-14, 1:00 p.m.
Recall from the Dijkstra's worksheet that if we can find values p[v] for each vertex v such that p[v] +
cost(u,v) = p[u] then we can run Dijkstra's with modified edge costs cost(u,v) + p[v] - p[u] and find
shortest paths even if some values c(u,v) are negative. But it did not specify how to find these values
p[], which are called potential values.
We find them using a slight modification of the Bellman-Ford algorithm. The modifications are as
follows:
there is no reached dictionary
there is no start vertex
initially dist[v] = 0 for every vertex v
Then run the main loop of the Bellman-Ford algorithm for |V|-1 steps. The claim is that afterward the
values -dist[v] for each vertex v are potential values if and only if the graph does not have a negativecost cycle.
Your Second Job
Implement the function to either find a potential or determine the graph has a negative-cost cycle.
That is, run the above algorithm and then check that the -dist[v] values are indeed potentials. If not,
return None. Otherwise, return these potential values as a dictionary.
def find_potential(vertices, edges):
'''
Finds a potential for the graph or determines the graph has
a negative-cost cycle.
vertices: the set of vertices in the graph.
edges: maps pairs of vertices to values representing edge costs
example - {('A', 'B'): -3} means the edge from vertex
'A' to vertex 'B' has cost -3
start: the start vertex to search from

If the graph has a negative-cost cycle, this simply returns None.
Otherwise, it returns a dictionary mapping each vertex to its value
in a potential function.
'''
Helpful Tests
The following graph may be helpful to test on. Examples of some function calls with this graph are
given below.
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
3 of 5 2018-04-14, 1:00 p.m.
Here is an example of using this graph in the functions.
vertices = {1, 2, 3, 4, 5, 6}
edges = {(1,2):5, (2,5):-7, (3,2):2, (4,1):-2, (5,1):3,
(5,3):6, (5,4):4, (6,3):2, (6,5):-10}
dist, reached = bellman_ford(vertices, edges, 1)
print(dist)
{1: 0, 2: 5, 3: 4, 4: 2, 5: -2}
print(reached)
{1: 1, 2: 1, 3: 5, 4: 5, 5: 2}
print(find_potential(vertices, edges))
{1: 8, 2: 3, 3: 4, 4: 6, 5: 10, 6: 0}
edges[(5,4)] = 3 # creates a negative-cost cycle
print(find_potential(vertices, edges))
None
Code Submission
Submit a single file called bellman_ford.py that includes the implementation of these two functions
and any functions you think might help. You must add some docstring tests to test these two
functions. We will run these tests via
python3 -m doctest -v bellman_ford.py
It is fine if you include these tests in the function documentation itself. Alternatively, you can just test
both functions in the docstring tests for the entire module (because typing out the graph description
more than once can be a pain). Seethis page for an example of using docstring tests for a whole
module.
Submit only the file bellman_ford.py, do not zip it. The above graph is ok to have as a test, but you
must create at least two more graphs to test on
Tips for Testing
Recall that we do not generally have control over which path is found so it would be sufficient to
ensure the reached dictionary has its keys being the reached vertices. But you can still test that the
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
4 of 5 2018-04-14, 1:00 p.m.
dist dictionary has the correct distances. Remember that docstring tests only check that the output
matches the expected output exactly (character for character), so it is tricky with dictionaries and sets
where we don't have control over the order things will be printed. I like to test things as follows:
dist[5]
-2
reached.keys == {1, 2, 3, 4, 5}
True
potential[5] + edges[(2,5)] = potential[2] # you don't have to do this for all edge
s if you don't want, just a few is ok
True
Submission status
Feedback
Attempt number This is attempt 1 ( 1 attempts allowed ).
Submission status Submitted for grading
Grading status Graded
Due date Monday, 5 February 2018, 11:55 PM
Time remaining Assignment was submitted 8 hours 12 mins early
Last modified Monday, 5 February 2018, 3:42 PM
File submissions
Export to portfolio
bellman_ford.py
Submission comments Comments (0)
Grade 100.00 / 100.00
Graded on Monday, 12 February 2018, 8:09 PM
Graded by Jason Cannon
Feedback comments Test Cases Passed: (50/50)
Bellman Ford - (25/25 passed)
Graph Potentials - (25/25 passed)
Final Mark: 100.0%
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
5 of 5 2018-04-14, 1:00 p.m.