Editor

Shortest Path in a Graph (BFS)

Advanced · Write the code · from 50 Python Practice Problems with Instant Answer Checking (Beginner to Advanced)

From the lesson: 50 Python Practice Problems with Instant Answer Checking (Beginner to Advanced)

Fifty problems, each with a code editor and real tests. Write your solution, press Check, and see exactly which cases pass. Stuck? Hints reveal one at a time, and the solution unlocks once you have checked at least once. Your code and progress are saved in this browser.

Read the lesson

A graph is a dict mapping each node to a list of neighbours. Write shortest_path(graph, start, goal) that returns the shortest path as a list of nodes, or None if goal cannot be reached. Explore neighbours in the order they are listed.

from collections import deque
def shortest_path(graph, start, goal):
pass
Solution unlocks after your first Check

What Check runs

Your code runs first, then each of these lines. The output must match exactly.

RunsExpected output
g = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []} print(shortest_path(g, "A", "F"))['A', 'B', 'D', 'F']
print(shortest_path({"A": ["B"], "B": [], "C": []}, "A", "C"))None

More practice problems

All Python exercises · 50 practice problems