import pdb
from collections import deque

graph = {'boston': set(['new york']),
         'new york': set(['pittsburg', 'philly']),
         'philly': set(['baltimore']),
         'baltimore': set(['washington']),
         'pittsburg': set(['minneapolis']),
         'washington': set(['minneapolis'])
         }



def bfs_paths(graph, start, goal):
    queue = deque()
    queue.append((start, [start]))
    result = []
    found = False
    #               node, path
    while queue:
        (vertex, path) = queue.popleft()
        for next in graph[vertex] - set(path):
            if next == goal:
                result.append(path + [next])
                found = True
            else:
                queue.append((next, path + [next]))
                # pdb.set_trace()
        if found:
            break

    return result


print(bfs_paths(graph, 'boston', 'minneapolis'))