The shortest way: breadth-first search

Depth-first search finds a way, not the shortest one. For the shortest you change the order: first all neighbours of the start, then their neighbours. You spread outward like rings from a stone dropped in water; the first time you reach a node you have reached it in the fewest steps. This is breadth-first search (BFS).

1from collections import deque
2queue = deque([(start, 0)])
3seen = {start}
4while queue:
5    node, steps = queue.popleft()
6    if node == goal:
7        return steps
8    for nxt in graph[node]:
9        if nxt not in seen:
10            seen.add(nxt)
11            queue.append((nxt, steps + 1))
12return -1

The only difference from DFS is a queue in place of the stack: first in, first out. The step count travels in the queue with the node. If the queue empties and the goal never came out, there is no way to it.

This holds where every step costs the same (one square on a grid, one move in a maze). With limited energy, or when looking for the nearest target, the distance as the crow flies misleads you: a near target behind a wall can cost more than a far one in the open. Measure the distance with BFS.

Tasks