Find a Shortest Unweighted Path with BFS
Return a shortest path in an unweighted adjacency-list graph using a FIFO queue.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Find a Shortest Unweighted Path with BFS
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
The first search finds A to B to D to G. Is it the shortest route? Run it, then look for the two-edge path that a stack skipped. The broken algorithm removes the last frontier item, so its list behaves as a stack. It reaches G through B and D and prints four nodes. That is a valid route, but the requirement is fewest edges. Returning the first goal works only when traversal order guarantees that shorter routes are explored first. Look at the actual order in which a list used as a stack visits branches. The last neighbor added is the first removed. On this graph that branch reaches G through B and D before the C branch gets its turn.
- 00:42
A-B-D-G has three links; A-C-G has two. Returning immediately at G is therefore unsafe with stack order. The error is observable even though every edge in the returned path is valid. A path-validity test alone would miss the broken shortest-path contract. The diagnosis prints candidate edge counts three and two, and shows A as the start. Breadth-first search uses a FIFO queue so all one-edge candidates are considered before two-edge candidates. The queue order supplies the shortest-path guarantee for an unweighted graph; changing only the frontier discipline changes the result. Trace the first two queue layers explicitly.
- 01:24
At distance zero we have A. At distance one, the outgoing neighbors are B and C. When those two are processed, the route through C can discover G at distance two before any distance-three candidate may be returned. That layer ordering is the proof behind the result, not a special property of node letters. Mark a neighbor seen as soon as it is put on the queue; otherwise two parents can enqueue the same node and waste work. The graph's neighbor order may change which shortest route appears when several routes share the same number of links. BFS promises the number of edges, not a lexicographically smallest path or a unique route.
- 02:04
In this test there is a strictly shorter alternative, so adjacency order cannot rescue the stack result. If a product needs a tie-break rule, sort neighbors or define that rule separately. Write down the queue after expanding A. The graph lists C before B, so A-C waits before A-B. Removing A-C appends A-C-G behind A-B. Removing A-B next appends A-B-D behind A-C-G. The two-edge goal path is therefore removed before the three-edge path even has a chance to extend to G. Changing neighbor order can change queue order within one layer, but it cannot put a new, longer path ahead of every shorter path already waiting.
- 02:46
That is the FIFO guarantee. The fixed version uses deque.popleft, marks neighbors seen when enqueuing, and prints A to C to G. Those three nodes mean two edges. For this small example it stores complete paths; a large graph could store each node's predecessor and reconstruct only the final route. Follow one queue operation in the source. popleft removes the oldest stored path. For each unvisited neighbor, the code creates the old path plus that neighbor and appends it to the right. The first time G is removed, the printed list is A, C, G. Count links between names rather than names: a three-node list has two edges.
- 03:27
The queue can hold several paths to different nodes, so the seen set bounds repeat work on a graph with cycles. For a larger graph, avoid storing the shared A prefix inside every queued path. Record parent of B as A, parent of C as A, and parent of G as C when each node is first discovered. Once G is reached, follow parent links backward: G, C, A. Reverse that sequence to display A, C, G. The queue then stores nodes rather than copies of growing path lists. The first parent assigned to G comes from a shortest route because discovery followed FIFO layers. The verifier prints the one-node path A when start equals goal, then None when a
- 04:08
goal is unreachable. The visited set prevents cycles from filling the queue forever. Breadth-first search minimizes hop count here; with unequal edge costs, the cheapest route needs a weighted-path algorithm. The one-node path for A to A is a useful boundary: no edge needs to be crossed. For an unreachable goal, None says that search exhausted the reachable component; an empty list would be ambiguous next to the zero-edge result. If the graph were weighted, a two-edge road might cost more than a three-edge road. This queue only certifies fewest links when all links have equal cost.
- 04:48
For huge graphs, store each predecessor once and reconstruct the route at the end. Consider a cycle A to B to A with a goal elsewhere. Without marking A and B as seen, the queue would keep adding longer copies of the same walk. Marking when enqueuing prevents those duplicates before they occupy memory. For a directed graph, follow only edges listed from the current node; for an undirected one, store both directions or build that view first.
Understand the concept
A dependency map contains links between nodes, and a learner wants the fewest edges from a start node to a goal node. Breadth-first search explores all paths of length one before length two, then length three. A FIFO queue preserves that order. The graph here is unweighted; weighted shortest paths need a different algorithm.
Using list.pop() treats the frontier as a LIFO stack, producing depth-first traversal. If the function returns the first goal it sees, it may return a longer route even though it technically found a route. A visually plausible answer is not enough when the contract says shortest.
Print the frontier order on a graph with both a two-edge and a three-edge route. The stack explores the longer branch first. With deque.popleft(), nodes are removed in insertion order, and each newly discovered path adds exactly one edge to a path already known to be shortest. Initialize deque with the path containing start. Pop paths from the left, append neighbor paths on the right, and mark a node visited when enqueuing it. Return the first path ending at goal. For this small teaching graph, storing whole paths is readable; larger graphs can store predecessor pointers instead.
If start equals goal, the shortest path is the one-node list. If no route exists, return None rather than an empty list that might be mistaken for a valid zero-edge path. The final run covers both conditions. Cycles must not lead to endless queue growth, so the visited set is part of the algorithm. BFS minimizes the number of edges only when edges have equal cost. It does not know that one route is geographically faster or cheaper than another. For large graphs, a queue of complete path copies consumes extra memory; reconstruct a path from parent pointers when scalability matters.
- A dependency map contains links between nodes, and a learner wants the fewest edges from a start node to a goal node.
- Using list.pop() treats the frontier as a LIFO stack, producing depth-first traversal.
- Initialize deque with the path containing start.
- If start equals goal, the shortest path is the one-node list.
See it step by step
Read the code, predict the output, then compare it with the result.
01. See FIFO traversal order
from collections import deque
q = deque(['A', 'B', 'C'])
print([q.popleft() for _ in range(3)])
['A', 'B', 'C']popleft visits the earliest enqueued node first.
02. Compare the two candidate lengths
long = ['A', 'B', 'D', 'G']
short = ['A', 'C', 'G']
print(len(long) - 1, len(short) - 1)
3 2The short route uses two edges while the long route uses three.
03. Use a visited set on a cycle
from collections import deque
graph = {'A':['B'], 'B':['A']}
q = deque(['A']); seen = {'A'}
while q:
node = q.popleft()
for nxt in graph[node]:
if nxt not in seen: seen.add(nxt); q.append(nxt)
print(sorted(seen))
['A', 'B']Marking nodes on enqueue prevents the A-B cycle from adding the same nodes forever.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
Observe the first result
A dependency map contains links between nodes, and a learner wants the fewest edges from a start node to a goal node. Breadth-first search explores all paths of length one before length two, then length three. A FIFO queue preserves that order. The graph here is unweighted; weighted shortest paths need a different algorithm.
popleft visits the earliest enqueued node first. Print the frontier order on a graph with both a two-edge and a three-edge route. The stack explores the longer branch first. With deque.popleft(), nodes are removed in insertion order, and each newly discovered path adds exactly one edge to a path already known to be shortest.
from collections import deque
q = deque(['A', 'B', 'C'])
print([q.popleft() for _ in range(3)])
['A', 'B', 'C']- Predict the first sample's printed value and type.
- Run it, then compare with the expected output.
Change the rule deliberately
Using list.pop() treats the frontier as a LIFO stack, producing depth-first traversal. If the function returns the first goal it sees, it may return a longer route even though it technically found a route. A visually plausible answer is not enough when the contract says shortest.
The short route uses two edges while the long route uses three. Initialize deque with the path containing start. Pop paths from the left, append neighbor paths on the right, and mark a node visited when enqueuing it. Return the first path ending at goal. For this small teaching graph, storing whole paths is readable; larger graphs can store predecessor pointers instead. Start with deque([(start, [start])]); use popleft(), add unseen neighbors on the right, and mark them seen when added.
long = ['A', 'B', 'D', 'G']
short = ['A', 'C', 'G']
print(len(long) - 1, len(short) - 1)
3 2- Identify the line that changes the rule.
- Run the corrected sample with the same input.
Verify the boundary
Print the frontier order on a graph with both a two-edge and a three-edge route. The stack explores the longer branch first. With deque.popleft(), nodes are removed in insertion order, and each newly discovered path adds exactly one edge to a path already known to be shortest. Initialize deque with the path containing start. Pop paths from the left, append neighbor paths on the right, and mark a node visited when enqueuing it. Return the first path ending at goal. For this small teaching graph, storing whole paths is readable; larger graphs can store predecessor pointers instead.
Marking nodes on enqueue prevents the A-B cycle from adding the same nodes forever. If start equals goal, the shortest path is the one-node list. If no route exists, return None rather than an empty list that might be mistaken for a valid zero-edge path. The final run covers both conditions. Cycles must not lead to endless queue growth, so the visited set is part of the algorithm. BFS minimizes the number of edges only when edges have equal cost. It does not know that one route is geographically faster or cheaper than another. For large graphs, a queue of complete path copies consumes extra memory; reconstruct a path from parent pointers when scalability matters.
from collections import deque
graph = {'A':['B'], 'B':['A']}
q = deque(['A']); seen = {'A'}
while q:
node = q.popleft()
for nxt in graph[node]:
if nxt not in seen: seen.add(nxt); q.append(nxt)
print(sorted(seen))
['A', 'B']- Try the documented edge case.
- Explain why the output satisfies the function contract.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Start with deque([(start, [start])]); use popleft(), add unseen neighbors on the right, and mark them seen when added.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
The visible failure
frontier.pop()frontier.popleft() using collections.dequeWhat happens: Using list.pop() treats the frontier as a LIFO stack, producing depth-first traversal.
Initialize deque with the path containing start. Pop paths from the left, append neighbor paths on the right, and mark a node visited when enqueuing it. Return the first path ending at goal. For this small teaching graph, storing whole paths is readable; larger graphs can store predecessor pointers instead.
Missing the edge condition
return [] when no route existsreturn None for unreachable goalWhat happens: If start equals goal, the shortest path is the one-node list.
BFS minimizes the number of edges only when edges have equal cost. It does not know that one route is geographically faster or cheaper than another. For large graphs, a queue of complete path copies consumes extra memory; reconstruct a path from parent pointers when scalability matters.