python 38 lines · 9 steps

Breadth-first search and shortest paths in Python

A queue-driven traversal that visits a graph level by level, then extends to track the shortest path between two nodes.

Explained by highlit
Intermediate graph-traversal bfs queue shortest-path algorithms
1from collections import deque
2 
3 
4def bfs(graph, start):
5 """Traverse a graph breadth-first, returning nodes in visit order."""
6 visited = {start}
7 order = []
8 queue = deque([start])
9 
10 while queue:
11 node = queue.popleft()
12 order.append(node)
13 for neighbor in graph[node]:
14 if neighbor not in visited:
15 visited.add(neighbor)
16 queue.append(neighbor)
17 
18 return order
19 
20 
21def shortest_path(graph, start, goal):
22 """Find the shortest path between two nodes using BFS."""
23 if start == goal:
24 return [start]
25 
26 visited = {start}
27 queue = deque([(start, [start])])
28 
29 while queue:
30 node, path = queue.popleft()
31 for neighbor in graph[node]:
32 if neighbor == goal:
33 return path + [neighbor]
34 if neighbor not in visited:
35 visited.add(neighbor)
36 queue.append((neighbor, path + [neighbor]))
37 
38 return None
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1BFS explores a graph in waves, so the first time it reaches a node is along a shortest edge-count path.
  2. 2Marking nodes visited at enqueue time — not dequeue time — prevents the same node from being queued multiple times.
  3. 3Carrying the path alongside each queued node turns plain BFS into a shortest-path finder.

Related explainers

python 
import argparse
import sys
from pathlib import Path
 

Building a subcommand CLI with argparse

cli argparse subcommands
Intermediate 6 steps
python 
from collections.abc import Mapping
from typing import Any, Iterator
 
 

Flattening nested config into dotted keys

recursion generators tree-traversal
Intermediate 7 steps
python 
import csv
import io
from datetime import datetime
 

Streaming a CSV export in Flask

streaming generators csv
Intermediate 9 steps
python 
import time
from collections import defaultdict
from threading import Lock
 

Sliding-window login rate limiting in Flask

rate-limiting sliding-window thread-safety
Intermediate 7 steps
python 
from django.conf import settings
from django.contrib.auth import get_user_model
from django.core.mail import EmailMultiAlternatives
from django.db.models.signals import post_save

Sending a welcome email with Django signals

signals email user-activation
Intermediate 8 steps
python 
import csv
import io
from datetime import date
 

Streaming a CSV export in FastAPI

streaming async-generators csv
Advanced 8 steps

Share this explainer

Here's the card — post it anywhere.

Breadth-first search and shortest paths in Python — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code