Fewest hops between two stations

Breadth-first search from the start explores stations in order of hop count, so the first time it reaches the goal is via the fewest hops. Keep a distance per station and mark stations as you queue them. O(V + E) time and space.

BFS is correct only because every track costs the same; with different costs use Dijkstra.

Bidirectional BFS (from both ends) can visit far fewer stations on large graphs.

Stop as soon as the goal is reached; no need to explore the rest.

from collections import deque


def fewest_hops(n: int, tracks: list[list[int]], start: int,
                goal: int) -> int:
    nbrs: list[list[int]] = [[] for _ in range(n)]
    # tracks run both ways
    for u, v in tracks:
        nbrs[u].append(v)
        nbrs[v].append(u)
    dist = [-1] * n
    dist[start] = 0
    queue = deque([start])
    while queue:
        s = queue.popleft()
        if s == goal:
            return dist[s]
        for t in nbrs[s]:
            if dist[t] < 0:
                dist[t] = dist[s] + 1
                queue.append(t)
    return -1

Common mistakes

• Using DFS, which finds a route but not necessarily the shortest.
• Marking stations when they are dequeued, which can queue the same station many times.

Say why BFS gives the fewest hops (layers in order of distance), then code it.

Follow-up questions

Think of your answer first, then open the hint.

1. How do you return the route itself?

   Show hint

   Store each station's parent and walk back from the goal.

2. What if some tracks are one-way?

   Show hint

   Build the adjacency list with directed edges; BFS is unchanged.