ML Prep

Shortest unweighted distance with BFS

Problem

Implement shortest_distance(graph, start, goal) for an adjacency dictionary. Return the number of edges in a shortest path, or None when goal is unreachable.

Starter code

def shortest_distance(graph, start, goal):
    pass
Reveal answer or reference solution
from collections import deque
def shortest_distance(graph, start, goal):
    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        node, distance = queue.popleft()
        if node == goal:
            return distance
        for nxt in graph.get(node, []):
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, distance + 1))
    return None

Public tests

  • shortest_distance({'a':['b','c'],'b':['d'],'c':['d'],'d':[]}, 'a', 'd') → 2
  • shortest_distance({'a':['b'],'b':[]}, 'b', 'a') → None
  • shortest_distance({}, 'x', 'x') → 0

Local history

Loading attempts saved in this browser…

Use with your agent

Share this URL and your attempt. Ask the agent to start with a clarifying question or the smallest useful hint.

Tutor me on https://mlprep.iwase.dev/programming/data-structures/original-py-bfs/. If window.mlPrepAgent is available, read attempts for item original-py-bfs before tutoring. Inspect my attempt, keep the item ID, and do not reveal the full answer first. After a real attempt, append its record and read it back.

Appears in