Graph: Implement Weighted Edges

Previously, you implemented a graph in Python. And you’ve implemented depth-first and breadth-first traversal for that graph. Now you’ll be adding weighting to the edges of the graph so that you can make a value judgement about the shortest path between two nodes.

Tasks

For your assignment tonight, implement a graph that allows your edges to have a weight. You may decide how exactly to do this, but here’s a description of one possible path to take:

The input graph G is assumed to have the following representation: A vertex can
be any object that can be used as an index into a dictionary.  G is a dictionary,
indexed by vertices.  For any vertex v, G[v] is itself a dictionary, indexed by the
neighbors of v.  For any edge v->w, G[v][w] is the length of the edge.  This is related
to the representation in <http://www.python.org/doc/essays/graphs.html> where
Guido van Rossum suggests representing graphs as dictionaries mapping vertices to
lists of neighbors, however dictionaries of edges have many advantages over lists:
they can store extra information (here, the lengths), they support fast existence tests,
and they allow easy modification of the graph by edge insertion and removal.  Such
modifications are not needed here but are important in other graph algorithms. Since
dictionaries obey iterator protocol, a graph represented as described here could be
handed without modification to an algorithm using Guido's representation.

(from http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ please, don't peek at this solution)

Your new graph should still support all the methods of your earlier implementation.

Create a new branch in your data-structures repository for this work. Add tests that demonstrate that your edges are weighted. Update your README with a description of your implementation and any references or collaborations you used to finish the assignment.

Submitting Your Work

When you are finished and all your tests are passing, create a new Pull Request in github from your working branch to master. Submit the URL for that pull request.

When you have submitted the assignment, you may merge your pull request, but please do not delete the branch you created for working on the assignment until the assignment has been graded in Canvas.

As usual, use the comments here in canvas to add any questions, comments or reflections on the work you did for this assignment.