This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Challenge Notebook¶

## Constraints¶

• Is this a directional graph?
• Yes
• Could the graph have cycles?
• Yes
• Note: If the answer were no, this would be a DAG.
• Are the edges weighted?
• Yes
• Note: If the edges were not weighted, we could do a BFS
• Are the edges all non-negative numbers?
• Yes
• Note: Graphs with negative edges can be done with Bellman-Ford
• Graphs with negative cost cycles do not have a defined shortest path
• Do we have to check for non-negative edges?
• No
• Can we assume this is a connected graph?
• Yes
• Can we assume the inputs are valid?
• No
• Can we assume we already have a graph class?
• Yes
• Can we assume we already have a priority queue class?
• Yes
• Can we assume this fits memory?
• Yes

## Test Cases¶

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


## Algorithm¶

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.

## Code¶

In [ ]:
%run ../../arrays_strings/priority_queue/priority_queue.py

In [ ]:
%run ../graph/graph.py

In [ ]:
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


## Unit Test¶

The following unit test is expected to fail until you solve the challenge.

In [ ]:
# %load test_shortest_path.py
import unittest

class TestShortestPath(unittest.TestCase):

def test_shortest_path(self):
graph = Graph()
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()


## Solution Notebook¶

Review the Solution Notebook for a discussion on algorithms and code solutions.