A graph is given as a dict from each node to the nodes it links to. Find the smallest number of edges from one node to another.

g = {"a": ["b", "c"], "b": ["d"],
     "c": ["d"], "d": []}
fewest_hops(g, "a", "d")  # 2

When edges have no weights, breadth-first search finds shortest paths. It explores everything one hop away, then two hops, and so on, so the first time it reaches a node is by a shortest route.

• Use a deque of (node, distance) pairs.
• Mark nodes as seen when you add them to the queue, not when you remove them. Otherwise a node can be queued many times.
• Without a seen set, a cycle would loop forever.

A node may appear only as a link and have no key of its own, so read neighbours with graph.get(node, []).

Write fewest_hops(graph, start, goal) returning the smallest number of edges from start to goal, or -1 if goal cannot be reached. If start equals goal, the answer is 0.

The explanation opens here once every check passes.