from heapq import heappush, heappop
import random

def shortest_path(a, b, graph):
    seen = set()
    h = []
    heappush(h, (0, a, [a]))
    while h:
        km, x, path = heappop(h)
        if x == b:
            return path
        for c in graph[x]:
            if c not in seen:
                heappush(h, (km + 1, c, path + [c]))
    raise Exception("We were unable to find a path from {} to {}".format(a, b))

graph = {
    'Min'     : ['William', 'Jayden', 'Omar'],
    'William' : ['Min', 'Noam'],
    'Jayden'  : ['Min', 'Amelia', 'Ren', 'Noam'],
    'Ren'     : ['Jayden', 'Omar'],
    'Amelia'  : ['Jayden', 'Adam', 'Miguel'],
    'Adam'    : ['Amelia', 'Miguel', 'Sofia', 'Lucas'],
    'Miguel'  : ['Amelia', 'Adam', 'Liam', 'Nathan'],
    'Noam'    : ['Nathan', 'Jayden', 'William'],
    'Omar'    : ['Ren', 'Min', 'Scott'],
    'Liam'    : ['Ren'],
    'Nathan'  : ['Noam'],
    'Scott'   : [],
}

result = shortest_path('Jayden', 'Adam', graph)
print(result)
assert result == ['Jayden', 'Amelia', 'Adam']
print('Success!')

beg = random.choice(list(graph.keys()))
end = random.choice(list(graph.keys()))
print("Attempting to find the shortest path between {} and {}".format(beg, end))
print(shortest_path(beg, end, graph))