Bridge · From syntax to engineering · 25 MIN

Find a shortest path through an unweighted graph

Breadth-first search explores every closer node before farther nodes.

Build adjacency lists, then use a deque as a FIFO queue. Mark nodes visited when they enter the queue to prevent repeated insertion through multiple edges. Each queued record stores a distance. The first time the target is removed from the queue, its distance is minimal because all shorter paths have already been explored. This argument depends on every edge having equal cost. Weighted edges need a different algorithm, such as Dijkstra for nonnegative weights.

Write a small contract first, then test how the implementation behaves at its boundaries.

Read the example

from collections import deque
queue = deque(["api", "db"])
print(queue.popleft())

api

Your challenge

Input {edges:list of [from,to] string pairs, start:string, end:string}. Edges are directed and unweighted. Return the minimum edge count from start to end, or -1 if unreachable. A node reaches itself in zero steps.

Solution cost: O(V + E). time · O(V + E) including the adjacency list. space

Common trap

A depth-first traversal finds a path but does not necessarily find the shortest path.

Further reading: Python deque