Graphs · stretch

Fewest hops

Write hops(graph, start, goal) returning the smallest number of edges from start to goal, or -1 if you cannot get there. hops(g, x, x) is 0.

Breadth-first search visits everything 1 hop away, then everything 2 hops away, and so on — so the first time it reaches goal is the shortest way. collections.deque gives you a queue.

right answers
arguments left as they should be

def hops(graph, start, goal):
    steps = 0
    place = start
    while place != goal:
        place = graph[place][0]
        steps += 1
    return steps

Run adds print(hops({"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}, "a", "d")) after your code, to try it.

Stuck on the idea rather than the code? The Graphs lesson walks through it.