This notebook was prepared by Donne Martin. Source and license info is on GitHub.
The constraints state we don't have to check for negative edges, so we test with the general case.
graph.add_edge('a', 'b', weight=5) graph.add_edge('a', 'c', weight=3) graph.add_edge('a', 'e', weight=2) graph.add_edge('b', 'd', weight=2) graph.add_edge('c', 'b', weight=1) graph.add_edge('c', 'd', weight=1) graph.add_edge('d', 'a', weight=1) graph.add_edge('d', 'g', weight=2) graph.add_edge('d', 'h', weight=1) graph.add_edge('e', 'a', weight=1) graph.add_edge('e', 'h', weight=4) graph.add_edge('e', 'i', weight=7) graph.add_edge('f', 'b', weight=3) graph.add_edge('f', 'g', weight=1) graph.add_edge('g', 'c', weight=3) graph.add_edge('g', 'i', weight=2) graph.add_edge('h', 'c', weight=2) graph.add_edge('h', 'f', weight=2) graph.add_edge('h', 'g', weight=2) shortest_path = ShortestPath(graph) result = shortest_path.find_shortest_path('a', 'i') self.assertEqual(result, ['a', 'c', 'd', 'g', 'i']) self.assertEqual(shortest_path.path_weight['i'], 8)
Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.
%run ../../arrays_strings/priority_queue/priority_queue.py
%load ../../arrays_strings/priority_queue/priority_queue.py
%run ../graph/graph.py
%load ../graph/graph.py
class ShortestPath(object):
def __init__(self, graph):
# TODO: Implement me
pass
def find_shortest_path(self, start_node_key, end_node_key):
# TODO: Implement me
pass
The following unit test is expected to fail until you solve the challenge.
# %load test_shortest_path.py
import unittest
class TestShortestPath(unittest.TestCase):
def test_shortest_path(self):
graph = Graph()
graph.add_edge('a', 'b', weight=5)
graph.add_edge('a', 'c', weight=3)
graph.add_edge('a', 'e', weight=2)
graph.add_edge('b', 'd', weight=2)
graph.add_edge('c', 'b', weight=1)
graph.add_edge('c', 'd', weight=1)
graph.add_edge('d', 'a', weight=1)
graph.add_edge('d', 'g', weight=2)
graph.add_edge('d', 'h', weight=1)
graph.add_edge('e', 'a', weight=1)
graph.add_edge('e', 'h', weight=4)
graph.add_edge('e', 'i', weight=7)
graph.add_edge('f', 'b', weight=3)
graph.add_edge('f', 'g', weight=1)
graph.add_edge('g', 'c', weight=3)
graph.add_edge('g', 'i', weight=2)
graph.add_edge('h', 'c', weight=2)
graph.add_edge('h', 'f', weight=2)
graph.add_edge('h', 'g', weight=2)
shortest_path = ShortestPath(graph)
result = shortest_path.find_shortest_path('a', 'i')
self.assertEqual(result, ['a', 'c', 'd', 'g', 'i'])
self.assertEqual(shortest_path.path_weight['i'], 8)
print('Success: test_shortest_path')
def main():
test = TestShortestPath()
test.test_shortest_path()
if __name__ == '__main__':
main()
Review the Solution Notebook for a discussion on algorithms and code solutions.