Searches a graph and returns the shortest (unweighted) path to the goal

UnweightedDijkstras.py

# returns the shortest path (measured in the number of edges) from start-->goal.
# if no path exists None is returned
def unweightedDijkstra(graph, start, goal):
    if goal is start:  # special case
        return (start,)

    q = [(start,)]  # q is a queue of paths (tuples of nodes)
    visited = set()

    while q:
        path = q.pop(0)
        current = path[-1]

        if current in visited:
            continue
        visited.add(current)

        for neighbour in graph[current]:
            if neighbour in visited:
                continue

            newPath = path + (neighbour,)

            if neighbour == goal:  # are we done?
                return newPath

            q.append(newPath)

    return None  # no we can't reach the goal



graph = {
    'A': ['B', 'D', 'G'],
    'B': ['A', 'E', 'F'],
    'C': ['F', 'H'],
    'D': ['A', 'F'],
    'E': ['B', 'G'],
    'F': ['B', 'C', 'D'],
    'G': ['A', 'E'],
    'H': ['C'],

    'I': ['J'],
    'J': ['I'],
}

print unweightedDijkstra(graph, 'A', 'H')
print unweightedDijkstra(graph, 'A', 'J')
print unweightedDijkstra(graph, 'J', 'J')
print unweightedDijkstra(graph, 'J', 'A')
print unweightedDijkstra(graph, 'C', 'A')